代码
int par[max_n]; //父亲数组
int rank[max_n]; //树的高度
void init(int n) { //初始化
for (int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
}
}
int find(int x) { //查询树的根
if (par[x] == x) return x;
else {
return par[x] = find(par[x]);
}
}
void unite(int x, int y) { //合并x,y所属的集合
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) par[x] = y;
else {
par[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
}
bool same(int x, int y) {
return find(x) == find(y);
}