并查集：(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。它支持以下两种操作:
　　－merge (Root1, Root2) //并操作；把子集合Root2并入集合Root1中.要求：Root1和 Root2互不相交,否则不执行操作.
　　－Find (x) //搜索操作；搜索单元素x所在的集合,并返回该集合的名字.
每个集合用一棵“有根树”表示
定义数组 set[1..n]
set[i] = i , 则i表示本集合，并是集合对应树的根
set[i] = j, j<>i, 则 j 是 i 的父节点.

Code

const int Max=1000;
int set[Max];
//初始化 for(i=0;i<Max;i++) set[i]=i;
int find(int x)//查找
{
    int i=x,r=x,j;
    while(set[r]!=r)
        r=set[r];
    while(i!=r)    //路径压缩
    {
        j=set[i];
        set[i]=r;
        i=j;
    }
    return r;
}
void merge(int a,int b)//归并
{
    int x,y;
    x=find(a);
    y=find(b);
    if(x!=y)
        set[x]=y;
}

转载于:https://www.cnblogs.com/wuying/archive/2008/08/14/1267868.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/97249614

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。