UnionFind
(data_structure/unionfind/unionfind.hpp)

• View this file on GitHub
• Last update: 2022-08-24 00:37:04+09:00
• Include: #include "data_structure/unionfind/unionfind.hpp"

UnionFind

集合を扱うデータ構造。

操作

• unionfind(N): $0, 1, \dots, N-1$ がそれぞれ異なる集合に属している状態で初期化する。
• root(x): $x$ が属する集合を代表する要素を $1$ つ答える。同じ集合の要素について root を行ったとき、同じ要素が返ることが保証される。
• same(x, y): $x, y$ が同じ集合に属するか判定する。
• unite(x, y): $x$ の属する集合と $y$ の属する集合を併合する。既に同じ集合に属する場合は何も発生しない。

資料

data-structures

Verified with

• test/aoj/dsl/dsl_1_a.test.cpp
• test/library_checker/data_structure/unionfind.test.cpp

Code

#pragma once
struct unionfind{
  vector<int> p;
  unionfind(int N){
    p = vector<int>(N, -1);
  }
  int root(int x){
    if (p[x] < 0){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x != y){
      if (p[x] < p[y]){
        swap(x, y);
      }
      p[y] += p[x];
      p[x] = y;
    }
  }
};

#line 2 "data_structure/unionfind/unionfind.hpp"
struct unionfind{
  vector<int> p;
  unionfind(int N){
    p = vector<int>(N, -1);
  }
  int root(int x){
    if (p[x] < 0){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x != y){
      if (p[x] < p[y]){
        swap(x, y);
      }
      p[y] += p[x];
      p[x] = y;
    }
  }
};

Back to top page