小解并查集（畅通工程+File Transfer）

什么是并查集呢？顾名思义就是对已知集合不停的合并与查找。

合并：对某两个集合进行操作

查找：查找某元素属于哪个集合

我们可以用树结构来表示每个集合，且用某个元素所在树的根节点表示该元素所在的集合，当判断两个元素是否属于同一集合石时只需判断他们的根节点即可。合并时也只需连接根节点。则{1，5}，{2，4，7，10}，{3，6，8，9}如下所示

例如要合并元素4和5，则只需找到相应的根节点进行连接即可。

小解并查集（畅通工程+File Transfer）

下面的例子是一个比较赤裸的入门级并查集----例题

小解并查集（畅通工程+File Transfer）

思路：先合并所给已知连通的结点(村庄)，再判断独立结点的个数即为所需的道路数目。

优化：修改元素x至根节点所遍历的元素的父亲节点，这样就减少了合并时间，如寻找元素20的根的情况，因为遍历了9，10。所以修改其父亲节点。

小解并查集（畅通工程+File Transfer）

下面是AC代码


#include<bits/stdc++.h>

#define maxsize 1005

using namespace std;

int parent[maxsize];

int n,m,x,y,counter,i;

int root(int num)//查找某元素的根节点

{

    int t=num;

    while(parent[num]!=num)//回溯寻找根

        num=parent[num];

    

    int temp;

    while(t!=num)//路径压缩

    {

        temp=parent[t];

        parent[t]=num;

        t=temp;

    }

}

void Merge(int x,int y)合并操作

{

    int px=root(x);

    int py=root(y);

 

    if(px!=py)

        parent[px]=py;

}

int main()

{

    while(scanf("%d",&n),n)

    {

        for(int i=1;i<=n;i++)//初始化所有元素为独立的根节点

            parent[i]=i;

        for(scanf("%d",&m);m>0;m--)

        {

            scanf("%d%d",&x,&y);

            Merge(x,y);

        }

        for(counter=0,i=1;i<=n;i++)

        {

            if(parent[i]==i)

                counter++;

        }

        printf("%d\n",--counter);//除去已合并的根节点

 

    }

 

    return 0;

 

}

*****************************************************************************************补充

其实对每个1--N的对象可以将它映射成0 -- N-1，即就是数组的顺序下标，然后数组内容用来存储每个节点所属集合的根节点，开始时全部初始化为-1，初始化为负数的一个好处就是判断根节点方便，还有就是可以赋予它的意义啊，让集合的根节点里存储该集合总的节点数量的负数，当然也可以存储该树的高度，这样都有利于后面的合并操作。。。。。。

合并：为了不让树的高度增加太快，可以使用秩合并，原则是小树贴到大树上。即判断两个集合的树高，或判断两个树的节点数量。选用后者可以与查找时的路径压缩完美契合.......

查找：用到路径压缩。

例题链接

#include<bits/stdc++.h>
using namespace std;
#define  maxsize 10005
int find_root(int *h,int m);
void merges(int *h,int x,int y);
void init(int n);
void check(int *h,int x,int y);
void Print(int n);
int n,x,y,h[maxsize];
char s;
int main()
{
    
    cin>>n;
    init(n);
    while(cin>>s)
    {
        if(s=='S')
        {
            Print(n);
            break;
        }
        cin>>x>>y;
        switch(s)
        {
            case 'C':check(h,x,y);break;
            case 'I':merges(h,x,y);break;

        }

    }

    return 0;
}
void init(int n)//根节点统一初始化为-1
{
    for(int i=0;i<n;i++)
        h[i]=-1;
}
int find_root(int *h,int m)//寻找根节点。。。回溯时改变所遍历节点的根节点。
{
    if(h[m]<0)
        return m;
    else
        return h[m]=find_root(h,h[m]);
}
void merges(int *h,int x,int y)//合并
{
    int r1=find_root(h,x);
    int r2=find_root(h,y);

    if(r1==r2)
        return;
    if(h[r1]>h[r2])//说明人r1的节点数量小，因为根节点存储的为负值，小树贴大树
    {
        h[r2]+=h[r1];
        h[r1]=r2;
    }
    else
    {
        h[r1]+=h[r2];
        h[r2]=r1;
    }

}
void check(int *h,int x,int y)//检查两个x,y是否连通。
{
    int r1=find_root(h,x);
    int r2=find_root(h,y);

    r1==r2?printf("yes\n"):printf("no\n");
}
void Print(int n)
{
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(h[i]<0)
            cnt++;
    }
    if(cnt==1)
        printf("The network is connected.\n");
    else
        printf("There are %d components.\n",cnt);
}

在这里列出两种合并时的方法，第一种就是按照集合树的节点数量比较，另一种是按照树的高度比较。

我在OJ上测试第一种方法稍快一点。。。

void merges(int *h,int x,int y)//按照节点数量合并
{
    int r1=find_root(h,x);
    int r2=find_root(h,y);

    if(r1==r2)//为同一集合直接返回不必操作
        return;
    if(h[r1]>h[r2])//说明人r1的节点数量小，因为根节点存储的为负值，小树贴大树
    {
        h[r2]+=h[r1];
        h[r1]=r2;
    }
    else
    {
        h[r1]+=h[r2];
        h[r2]=r1;
    }

}


void merges(int *h,int x,int y)//按照树的高度合并
{
    int r1=find_root(h,x);
    int r2=find_root(h,y);

    if(r1==r2)
        return;
    if(h[r1]>h[r2])
        h[r1]=r2;
    else if(h[r1]<h[r2])
        h[r2]=r1;
    else
    {
        h[r1]--;//两个集合树高度相等合并树高加1，因为存储的是负数，所以做--操作
        h[r2]=r1;
    }

}

小解并查集（畅通工程+File Transfer）

相关推荐