競技プログラミング（競プロ）では、集合を管理するデータ構造「Union-Find（ユニオンファインド）」が頻出です。この記事では、C++で使えるUnion-Findの自作ライブラリを紹介し、効率的な実装例と使い方を解説します。
Union-Findライブラリの概要
Union-Findは、「要素がどの集合に属しているか」を管理しつつ、集合の統合（union）や判定（find）を高速に行うデータ構造です。
C++を用いて配列ベースで簡潔に実装しているので、競プロでも即戦力になります。
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
constructor(n) |
n 個の頂点集合を作る |
$O(n)$ |
unite(x, y) |
x が属すグループと y が属すグループを合併する |
ほぼ$O(1)$ |
int root(int x) |
xが属すグループの代表のIDを返す |
ほぼ$O(1)$ |
is_same(x, y) |
x と y が同じグループか？を返す |
ほぼ$O(1)$ |
size(x) |
x が属すグループの要素数を返す |
ほぼ$O(1)$ |
size() |
グループの種類数を返す | $O(1)$ |
C++での Union-Find 実装例
struct UnionFind {
public:
///////////////メンバ変数↓////////////////////
vector<int> par; // par[i] : iの親の番号 (例) par[3] = 2 : 3の親が2
vector<int> count_size; //count_size[i] := iを根とした部分技のサイズ
int count_group; //全体として何個の集合があるか
/////////////コンストラクタ↓////////////////////
//最初は全てが根として初期化
UnionFind(int n) : par(n),count_size(n),count_group(n) {
for(int i=0;i<n;i++){
par[i] = i;
count_size[i] = 1;
}
}
///////////////メンバ関数↓////////////////////
// xが属すグループの根を返す関数
int root(int x) {
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
// xが属すグループと、yが属すグループを合併する関数
void unite(int x, int y) {
//x、yの根が同じ（既に同じグループ）ときは何もしない
int rx = root(x);
int ry = root(y);
if (rx == ry) return;
//yが属すグループを主として、xが属すグループをくっつける
par[rx] = ry;
count_size[ry] += count_size[rx];
count_group--;
}
// x, yが同じグループに属すか？を返す関数
bool is_same(int x, int y) {
int rx = root(x);
int ry = root(y);
return rx == ry;
}
// xが属すグループの要素数を返す関数
int size(int x){
return count_size[root(x)];
}
// グループの種類数を返す関数
int size(){
return count_group;
}
};
使用例
#include<bits/stdc++.h>
using namespace std;
//--ここにUnionFindライブラリ--//
// //
//--------------------------//
int main(){
//要素数10で作る
UnionFind uf(10);
//頂点2と、頂点4を合併
uf.unite(2,4);
//頂点2と、頂点4が同じグループか？
if(uf.is_same(2,4)){
cout << "2と4は同じグループ" << endl;
}
//頂点2が属すグループのサイズ
int sz = uf.size(2);
//グループがいくつあるか？
int gsz = uf.size();
}
注意点・Tips
- 頂点番号は
0-indexedで扱っています - 計算量の「ほぼ$O(1)$」とは、「$O(\alpha(N))$」のことです。もっとちゃんと知りたい方はUnion Find の計算量の話に詳しく書いてあります
実際に使ってみる
AtCoder Typical Contest 001 - B問題
ACコード↓
#include<bits/stdc++.h>
using namespace std;
//--ここにUnionFindライブラリ--//
// //
//--------------------------//
// グローバル変数
int N, Q;
int main(){
// 入力
cin >> N >> Q;
// UnionFindTreeを作成
UnionFind uf(N);
// 各クエリを処理
while(Q--){
// クエリの入力
int p, a, b;
cin >> p >> a >> b;
// 連結クエリの場合
if(p == 0){
uf.unite(a, b);
}
//判定クエリの場合
else{
if(uf.is_same(a, b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
}