一:并查集的基本操作:
1.初始化:
让每个节点的父节点指向本身
void init() {
for (int i = 0; i < N; i++) fa[i] = i;
}
2.查询:
用递归的方法查询此节点的根节点,一层一层访问父节点,直至根节点(根节点的标志就是父节点是本身)。要判断两个元素是否属于同一个集合,只需要看它们的根节点是否相同即可。
int find(int x) {
return fa[x] == x ? x : find(fa[x]);
}
3.合并:
1.合并1—3:

2.接着合并1—2,4—5,4—6,1—4.

先找到两个集合的代表元素,然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者
void merge(int a, int b) {
fa[find(a)] = find(b);//把a的根节点并到b的根节点上
}
例1:How Many Tables
题意:
