This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#include "graph/bipartite_coloring.hpp"
int main() {
std::mt19937 rng(20261029);
for (int trial = 0; trial < 2000; trial++) {
int n = 1 + rng() % 10;
int m = rng() % 14;
std::vector<std::pair<int, int>> edges;
std::set<std::pair<int, int>> es;
bipartite_coloring g(n);
for (int i = 0; i < m; i++) {
int u = rng() % n, v = rng() % n;
if (trial % 4 == 0 && u == v) continue;
edges.emplace_back(u, v);
es.emplace(u, v);
es.emplace(v, u);
g.add_edge(u, v);
}
g.build();
bool expect = false;
for (int mask = 0; mask < (1 << n) && !expect; mask++) {
bool ok = true;
for (auto [u, v] : edges) ok &= ((mask >> u & 1) != (mask >> v & 1));
expect |= ok;
}
assert(g.is_bipartite() == expect);
assert(g.odd_cycle().empty() == expect);
for (int v = 0; v < n; v++) assert(g.color(v) == 0 || g.color(v) == 1);
if (expect) {
for (auto [u, v] : edges) assert(g.color(u) != g.color(v));
} else {
const std::vector<int>& c = g.odd_cycle();
int k = int(c.size());
assert(k % 2 == 1);
std::set<int> seen(c.begin(), c.end());
assert(int(seen.size()) == k);
for (int i = 0; i < k; i++) assert(es.count({c[i], c[(i + 1) % k]}));
}
}
std::cout << "Hello World\n";
}#line 1 "test/unit/bipartite_coloring.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>
#line 2 "graph/bipartite_coloring.hpp"
#include <algorithm>
#line 4 "graph/bipartite_coloring.hpp"
#include <utility>
#line 6 "graph/bipartite_coloring.hpp"
struct bipartite_coloring {
public:
bipartite_coloring() : bipartite_coloring(0) {
}
explicit bipartite_coloring(int n) : _n(n), g(n), _color(n, -1) {
}
void add_edge(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
g[u].push_back(v);
g[v].push_back(u);
}
void build() {
_color.assign(_n, -1);
_cycle.clear();
std::vector<int> par(_n, -1), it(_n, 0), st;
for (int s = 0; s < _n; s++) {
if (_color[s] != -1) continue;
_color[s] = 0;
st.assign(1, s);
while (!st.empty()) {
int u = st.back();
if (it[u] == int(g[u].size())) {
st.pop_back();
continue;
}
int v = g[u][it[u]++];
if (_color[v] == -1) {
_color[v] = _color[u] ^ 1;
par[v] = u;
st.push_back(v);
} else if (_color[v] == _color[u] && _cycle.empty()) {
for (int x = u; x != v; x = par[x]) _cycle.push_back(x);
_cycle.push_back(v);
std::ranges::reverse(_cycle);
}
}
}
}
bool is_bipartite() const {
return _cycle.empty();
}
int color(int v) const {
assert(0 <= v && v < _n);
return _color[v];
}
const std::vector<int>& odd_cycle() const {
return _cycle;
}
private:
int _n;
std::vector<std::vector<int>> g;
std::vector<int> _color, _cycle;
};
#line 9 "test/unit/bipartite_coloring.test.cpp"
int main() {
std::mt19937 rng(20261029);
for (int trial = 0; trial < 2000; trial++) {
int n = 1 + rng() % 10;
int m = rng() % 14;
std::vector<std::pair<int, int>> edges;
std::set<std::pair<int, int>> es;
bipartite_coloring g(n);
for (int i = 0; i < m; i++) {
int u = rng() % n, v = rng() % n;
if (trial % 4 == 0 && u == v) continue;
edges.emplace_back(u, v);
es.emplace(u, v);
es.emplace(v, u);
g.add_edge(u, v);
}
g.build();
bool expect = false;
for (int mask = 0; mask < (1 << n) && !expect; mask++) {
bool ok = true;
for (auto [u, v] : edges) ok &= ((mask >> u & 1) != (mask >> v & 1));
expect |= ok;
}
assert(g.is_bipartite() == expect);
assert(g.odd_cycle().empty() == expect);
for (int v = 0; v < n; v++) assert(g.color(v) == 0 || g.color(v) == 1);
if (expect) {
for (auto [u, v] : edges) assert(g.color(u) != g.color(v));
} else {
const std::vector<int>& c = g.odd_cycle();
int k = int(c.size());
assert(k % 2 == 1);
std::set<int> seen(c.begin(), c.end());
assert(int(seen.size()) == k);
for (int i = 0; i < k; i++) assert(es.count({c[i], c[(i + 1) % k]}));
}
}
std::cout << "Hello World\n";
}