UnionFind
(graph/UnionFind.hpp)

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

説明

• Constructor

  UnionFind(int n)
  

• 頂点x,yを接続

  bool unite(int x, int y)
  

• 同じ集合か判定

  bool same(int x, int y)
  

• その頂点を含む集合の大きさを求める

  int size(int x)
  

Required by

• graph/check-bipartite.hpp
• Kruskal法(最小全域木) (graph/kruskal.hpp)

Verified with

• test/aoj/GRL/GRL_2_A.test.cpp
• test/yosupo/Data-Structure/Unionfind.test.cpp

Code

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 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)];
  }
};

Back to top page