并查集

并查集维护一个集合，并实现union和find两种操作。

并查集采用父指针法存储若干棵树，来表示若干个集合，用集合的根结点的编号区分不同集合；

set[i]存储结点i的父结点的编号，父结点编号和自身相等的结点为集合的根结点；

int set[n];

for (int i = 0; i < n; i++) set[i] = i;

find操作，按照父指针一直找到根结点，同时将经过的所有点的父结点全部修改为根节点（路径压缩）：

int find(int x) {
    if (set[x] != x) set[x] = find(set[x]);
    return set[x];
}

union操作，直接将a所在集合的根结点的父结点指向b所在集合的根结点，一般不用按秩合并，对效率的影响不大：

set[find(a)] = find(b);

注解：

(1)可以在并查集中维护集合结点个数：

只有当i为根结点时，cnt[i]才有意义，表示此集合的结点数目；

int cnt[n];

for (int i = 0; i < n; i++) cnt[i] = 1;

find操作不变，union操作时，需要更新集合结点个数：

cnt[find(b)] += cnt[find(a)]; // 此操作必须在 set[find(a)] = find(b) 之前完成

---