本文共 2491 字，大约阅读时间需要 8 分钟。

1；初始化；据具体情况保存和初始化需要的内容 ；

初始化必须要进行的。把每个节点所在集合初始化为其自身。O(n)

//初始化；划分类，就是有多少个元素就有多少个等价类         for(i = 1; i <= n; i++){
  //要从1开始；             ba[i] = i;//初始化；         }

2；查找；查找该元素所在集合；

没压缩版；

int find(int a)//无压缩的查找 ,找根节点，用函数find(a)找到a的最近的祖先。 {    while(ba[a] != a){//当祖先不等于编号时；         a = ba[a];//将祖先的编号赋值给a；     }    return a;//返回a的最近祖先；(这里的祖先就是前面一个) }

3；合并

void marget(int a, int b)//先找到a，b各自的祖先然后再把祖先链接起来； {    int fa = find(a);//将各自的祖先赋值下来     int fb = find(b);     if(fa != fb){
  //如果两个的祖先不是同一个祖先         ba[fa] = fb;//则将编号fa的祖先赋值为 fb(也就是b的祖先)下面会有模拟的。     }}

4；最先祖先的个数；要输出有好多个最先祖先；只需要判断pa[i]==i;

count = 0;//这里视情况而定        for(i = 1; i <= n; i++){            if(ba[i] == i){
  //等下又模拟的；                count++;//count就是表示最先祖先的个数            }        }

4压缩版的查找

//找到该元素所在集合的最初元素；

找元素所在集合的代表元(因为用了路径压缩，路径压缩的主要目的是为了尽快的确定元素所在的集合）

int findset(int v)      //循环{      int t1,t2=v;      while(v!=pa[v])  //与前面一样的，找到v**最近**的祖先         v=pa[v];      while(t2!=pa[t2]){ //找到v**最先**的祖先；            t1=pa[t2];          pa[t2]=v;          t2=t1;      }      return v;  }

int findset(int x)//递归{    if (x != pa[x])   {      pa[x] = findset(pa[x]);    }    return pa[x];}

来模拟一下是怎么实现并查集的吧？

我以下的祖先，也表示了父亲，就是把凡是可以生成它的都是他的祖先；方便描述点； 定义一个数组pa[100000]; pa的下标表示该元素的编号； pa的内容表示该元素的祖先；

1；最前面的初始化应该知道吧；就是把每个元素的祖先都定义为自己；

2；查找那里；就是当ba[a] != a时就是a的祖先不是a，表示a有祖先了。就将它最近的祖先返回；而那个压缩的就是返回它的最前面的祖先。

3；合并；就是判断ab的祖先是不是出自同一祖先，如果不是就将pa[a1]=b1;意思就是说把编号为a1(就是a的祖先)的祖先赋值为b1；

下面来模拟一遍吧；

定义数组s； s==下标==1 | 2 | 3 | 4 | 5 | 6 | 7 | 8;

===内容= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8；最前面初始化；

1 2连接== 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8；将pa[1]=2;就是这个代码； 3 4连接== 2 | 2 | 4 | 4 | 5 | 6 | 7 | 8 ；将pa[3]=4;就是这个代码； 1 4连接== 2 | 4 | 4 | 4 | 5 | 6 | 7 | 8；将pa[2]=4;就是这个代码； 突然间是不是更晕了，然而答案已近出来了。 用判断pa[i]==i;来判断count求出最先祖先的个数； 就是5；是不是；答案就是5啊、意思就是我们的代码作用就是留下pa[i]=i;

看一个套用模板的题目；

hdu1232畅通工程； 套用模板得出；

#include
   
    int ba[1004]={
  0};int find(int a){    while(ba[a] != a){        a = ba[a];    }    return a;}void marget(int a, int b){    int fa = find(a);    int fb = find(b);    if(fa != fb){        ba[fa] = fb;    }}int main(){    int n, m, i,a,b,count;    while(scanf("%d %d",&n, &m)!=EOF&&n!=0){        for(i = 1; i <= n; i++){            ba[i] = i;//初始化；         }         for(i = 1; i <= m; i++){            scanf("%d %d",&a, &b);            marget(a, b);        }        count = -1;//这里是求要多少个路，则是从-1开始        for(i = 1; i <= n; i++){            if(ba[i] == i){                count++;            }        }        printf("%d\n",count);    }    return 0 ;}
   

转载地址：https://blog.csdn.net/zw1996/article/details/51317364 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！