graph/check-bipartite.hpp

View this file on GitHub
Last update: 2023-03-13 15:00:41+09:00
Include: #include "graph/check-bipartite.hpp"

Depends on

Code

#include "template.hpp"
#include "UnionFind.hpp"

template <class T>
bool is_bipartite(const Graph<T> &g){
  const int n = g.size();
  UnionFind tree(n * 2);
  for(int i = 0; i < n; i++) for(const auto &x : g[i]){
    tree.unite(x.from, x.to+n);
    tree.unite(x.from+n, x.to);
  }
  for(int i = 0; i < n; i++) for(const auto &x : g[i]){
    if(tree.same(x.from, x.to+n)) return false;
  }
  return true;
}

#line 2 "graph/template.hpp"

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;
#line 1 "graph/UnionFind.hpp"
struct UnionFind {
  private:
  int n;
  public:
  vector<int> d;
  UnionFind(int n): n(n), d(n, -1){}
  int root(int x){
    assert(0 <= x && x < n);
    if(d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  int size(int x){
    return -d[root(x)];
  }
};
#line 3 "graph/check-bipartite.hpp"

template <class T>
bool is_bipartite(const Graph<T> &g){
  const int n = g.size();
  UnionFind tree(n * 2);
  for(int i = 0; i < n; i++) for(const auto &x : g[i]){
    tree.unite(x.from, x.to+n);
    tree.unite(x.from+n, x.to);
  }
  for(int i = 0; i < n; i++) for(const auto &x : g[i]){
    if(tree.same(x.from, x.to+n)) return false;
  }
  return true;
}