structure/union-find/bipartite-graph.hpp

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "structure/union-find/bipartite-graph.hpp"

Code

struct BipartiteGraph : UnionFind {
  vector<int> color;

  BipartiteGraph(int v) : color(v + v, -1), UnionFind(v + v) {}

  bool bipartite_graph_coloring() {
    for (int i = 0; i < color.size() / 2; i++) {
      int a = find(i);
      int b = find(i + (int)color.size() / 2);
      if (a == b) return (false);
      if (color[a] < 0) color[a] = 0, color[b] = 1;
    }
    return (true);
  }

  bool operator[](int k) { return (bool(color[find(k)])); }
};

#line 1 "structure/union-find/bipartite-graph.hpp"
struct BipartiteGraph : UnionFind {
  vector<int> color;

  BipartiteGraph(int v) : color(v + v, -1), UnionFind(v + v) {}

  bool bipartite_graph_coloring() {
    for (int i = 0; i < color.size() / 2; i++) {
      int a = find(i);
      int b = find(i + (int)color.size() / 2);
      if (a == b) return (false);
      if (color[a] < 0) color[a] = 0, color[b] = 1;
    }
    return (true);
  }

  bool operator[](int k) { return (bool(color[find(k)])); }
};

Back to top page