1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int par[MAX_N];//每个节点的父节点
int rank[MAX_N];//树的高度
//初始化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]);//递归向上查询,查询到之后直接连到根
}
}

//合并x和y所属的集合
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y)return;//xy已经在一组
if (rank[x] < rank[y]) { //x的高度小于y,则y作为新的根
par[x] = y;
}
else {
par[y] = x;
if (rank[x] == rank[y])rank[x]++;//若两树高度相同,则取x为新根,高度+1
}
}

//判断x和y是否属于同一集合
bool same(int x, int y) {
return find(x) == find(y);//根相同
}