【自分用メモ】Union-Find木
Union-Find木のコード
参考書
Union-Find木とは…
・グループ分けを管理するデータ構造
・根が同じ場合同じグループとする
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define MAX_V ノードの数 int par[MAX_V]; //ノードiの親=par[i] int rnk[MAX_V]; //深さ //配列の初期化 //最初は自分が根 void init(int V){ FOR(i, 0, V){ par[i] = i; rnk[i] = 0; } } //根を探す int find(int x){ if(par[x] == x) return x; return par[x] = find(par[x]); } //合併 void unite(int x, int y){ x = find(x);//xの根 y = find(y);//yの根 if(x == y) return; //深い方にくっつける if(rnk[x]>=rnk[y]){ par[y] = x; if(rnk[x]==rnk[y]) rnk[x]++; } else{ par[x] = y; } } //同じグループかどうか bool same(int x, int y){ return find(x) == find(y) }