《数据结构》——并查集

并查集，一种简单的集合表示

1. Initial()
2. Union()
3. Find()

有三种操作：

1. Initial(S)，初始化集合S；

2. Union(S,root1,root2)，把S中互不相交的子集合并在一起；

3. Find(S,x)，查找S中元素x所在的子集合，并返回该子集合的根结点。

通常用树、森林的“双亲表示法”作为并查集的存储结构。每个子集用一棵树表示；所有子集的树构成全集和的森林。如下图：

也可以再简化：

下面是找某元素所在子集的操作（并把 x 的根作为记录直接记到 S[x] 中，修改数组，方便下次查找）。代码如下：

#include<stdio.h>
int main(){
    int a[10] = {-6,0,-4,2,1,2,0,5,0,1};
    int r = Find(&a, 9);
    printf("root: %d\n", r);
}

int Find(int s[], int x){
    int root = x;
    int t;
    while(s[root] >= 0){
        root = s[root];
    }
    while(x != root){  //从x往回改
        t = s[x];
        s[x] = root;
        x = t;
    }
    return root; 
}