library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/bipartite_coloring.test.cpp

Depends on

Code

#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";
}
Back to top page