数据结构之并查集(Union-Find)

忘是亡心i 2022-08-04 01:48 115阅读 0赞

叫做并查集的主要原因是该数据结构的主要操作是：

1：合并区间（union）

2：查找元素所属区间（find）

所以叫做并查集

如果给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。

问题：若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

要解决这个问题或许可以使用图论，最后判断两个人是否在一个连通子图中，但是考虑到复杂度等我们发现这样并不好处理并且当数据很多的时候会很费时间。这时候我们考虑使用并查集。

就动态连通性这个场景而言，我们需要解决的问题可能是：

给出两个节点，判断它们是否连通，如果连通，不需要给出具体的路径

给出两个节点，判断它们是否连通，如果连通，需要给出具体的路径

就上面两种问题而言，虽然只有是否能够给出具体路径的区别，但是这个区别导致了选择算法的不同，本文主要介绍的是第一种情况，即不需要给出具体路径的Union-Find算法，而第二种情况可以使用基于DFS的算法。

思想基本都体现在下面的一步一步改进的代码中了，请仔细看。

//简单数组，也可看做是使用了链表的数组化
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <string>
    //#include <queue>
    //#include <algorithm>
    //#include <cmath>
    //#include <iomanip>
    //#include <stack>
    //using namespace std;
    //
    //const int maxn = 1000005;
    //int a[maxn];   //a[i]表示的是结点i的组号，初始值是
    //int n,m,coun;//count记录一共有多少组
    //
    //int find(int ind)
    //{
    //    return a[ind];//查找ind的组号
    //}
    //
    //void unio(int p,int q)
    //{
    //    int pID=find(p);
    //    int qID=find(q);//获得p和q的组号
    //    if(pID==qID)return ;
    //    for(int i = 0 ; i < n ; i++)
    //    {
    //        if(a[i]==pID)a[i]=qID;
    //        //将两组合并，组号都变为qID
    //    }
    //    coun--;//组数减少1
    //}
    //
    //int main()
    //{
    //    while(1)
    //    {
    //        int p,q;
    //        scanf("%d%d",&n,&m);
    //        coun=n;//初始时候每个节点都是一组
    //        for(int i = 0 ; i < n ; i++)
    //        {
    //            a[i]=i;
    //        }
    //        for(int i = 0 ; i < m ; i++)
    //        {
    //            scanf("%d%d",&p,&q);//表示结点p和q连通
    //            unio(p,q);
    //        }
    //        int t = 4;
    //        while(t--)
    //        {
    //            scanf("%d%d",&p,&q);
    //            if(find(p)==find(q))printf("YES\n");
    //            else printf("NO\n");
    //        }
    //    }
    //    return 0;
    //}
    最简单的并查集，可以看到unio函数每次更新结点所属的组号的时候
    时间复杂度是O(n),这样总的时间复杂度就是O(m*n),可能会超时

使用树形结构
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <string>
    //#include <queue>
    //#include <algorithm>
    //#include <cmath>
    //#include <iomanip>
    //#include <stack>
    //using namespace std;
    //
    //const int maxn = 1000005;
    //int a[maxn];   //a[i]表示的是结点i的组号，初始值是
    //int n,m,coun;//count记录一共有多少组
    //
    //int find(int p)
    //{
    //    while(p!=a[p])p=a[p];
    //    return p;//查找p的组号(根节点)
    //}
    //
    //void unio(int p,int q)
    //{
    //    int pRoot=find(p);
    //    int qRoot=find(q);//获得p和q的组号
    //    if(pRoot==qRoot) return ;
    //    a[pRoot]=qRoot;//之后将根节点改变就相当于将该组的所有节点所在组都改论了
    //    coun--;//组数减少1
    //}
    //
    //int main()
    //{
    //    while(1)
    //    {
    //        int p,q;
    //        scanf("%d%d",&n,&m);
    //        coun=n;//初始时候每个节点都是一组
    //        for(int i = 0 ; i < n ; i++)
    //        {
    //            a[i]=i;
    //        }
    //        for(int i = 0 ; i < m ; i++)
    //        {
    //            scanf("%d%d",&p,&q);//表示结点p和q连通
    //            unio(p,q);
    //        }
    //        int t = 4;
    //        while(t--)
    //        {
    //            scanf("%d%d",&p,&q);
    //            if(find(p)==find(q))printf("YES\n");
    //            else printf("NO\n");
    //        }
    //    }
    //    return 0;
    //}
    //树形结构容易出现极端情况，即所有的子节点在一行形成一个链表
    //这时候在查找的时候会很浪费时间。

//其实现在这颗树已经很节减了，但我们永远要追求更完美，那么怎么样才能使
    //结果更完美呢，我们看到现在我们所有的操作的时间都花费在查找函数上面了，
    //那查找函数还可以在压缩一下时间吗，这腰取决于这颗树是怎么样的。假如每一
    //颗树的深度都是1，也就是说所有的结点都直接挂在根结点上面，那么这棵树
    //是不是查找起来很方便了。但这是理想状态，很难达到，但是我们可以尽可能的
    //使数的深度更小。
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <iomanip>
    #include <stack>
    using namespace std;
    
    const int maxn = 1000005;
    int a[maxn];   //a[i]表示的是结点i的组号，初始值是
    int s[maxn];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
    int n,m,coun;  //count记录一共有多少组
    
    int Find(int p)
    {
         //一种更好的路径压缩
         //二分压缩路径（compresses paths by halving）：
         //具体思想就是把当前的结点，跳过一个指向父亲的父亲，
         //从而使整个路径减半深度减半。
         //这种办法比满路径压缩要快那么一点点。数据越大，当然区别就会越明显。
        while(p!=a[p])
        {
            a[p]=a[a[p]];
            //添加这样一行代码，将每个节点都挂在原父节点的
            //父节点上面，查找的时间复杂度至少少一半
            //路径压缩,在集合的查找过程中顺便将树的深度降低
            p=a[p];
        }
        return p;//查找p的组号(根节点)
    
    
        //满路径压缩（full compresses paths）：这是一种极其简单但又很常用的方法。
        //就是在添加另一个集合的时候，把所有遇到的结点都指向根节
    //    if(p!=a[p])
    //        a[p]=Find(a[p]);
    //    //在递归回来的时候把路径上元素的父亲指针都指向根结点。
    //    return a[p];
    
    }
    
    void Union(int p,int q)
    {
        int pRoot=Find(p);
        int qRoot=Find(q);//获得p和q的组号
        if(pRoot==qRoot) return ;
        //将小数作为大数的子树
        //按秩进行合并
        if(s[pRoot]<s[qRoot])
        {
            a[pRoot]=qRoot;
            s[qRoot]+=s[pRoot];
        }
        else
        {
            a[qRoot]=pRoot;
            s[pRoot]+=s[qRoot];
        }
        //之后将根节点改变就相当于将该组的所有节点所在组都改论了
        coun--;//组数减少1
    }
    
    int main()
    {
        while(1)
        {
            int p,q;
            scanf("%d%d",&n,&m);
            coun=n;//初始时候每个节点都是一组
            for(int i = 0 ; i < n ; i++)
            {
                a[i]=i;s[i]=1;
            }
            for(int i = 0 ; i < m ; i++)
            {
                scanf("%d%d",&p,&q);//表示结点p和q连通
                Union(p,q);
            }
            int t = 4;
            while(t--)
            {
                scanf("%d%d",&p,&q);
                if(Find(p)==Find(q))printf("YES\n");
                else printf("NO\n");
            }
        }
        return 0;
    }

//我们考虑一下上面代码中的unio函数中的这一段，a[pRoot]=qRoot;
    //有没有问题呢，一看好像没有问题，一个简简单单的赋值操作。但是我们
    //看到这个操作是直接赋值的，并没有进行什么判断，其实我们每次需要的
    //是将一颗比较小的数挂在一颗大一点的数上面,所以需要判断
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <string>
    //#include <queue>
    //#include <algorithm>
    //#include <cmath>
    //#include <iomanip>
    //#include <stack>
    //using namespace std;
    //
    //const int maxn = 1000005;
    //int a[maxn];   //a[i]表示的是结点i的组号，初始值是
    //int s[maxn];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
    //int n,m,coun;  //count记录一共有多少组
    //
    //int find(int p)
    //{
    //    while(p!=a[p])p=a[p];
    //    return p;//查找p的组号(根节点)
    //}
    //
    //void unio(int p,int q)
    //{
    //    int pRoot=find(p);
    //    int qRoot=find(q);//获得p和q的组号
    //    if(pRoot==qRoot) return ;
    //    //将小数作为大数的子树
    //    if(s[pRoot]<s[qRoot])
    //    {
    //        a[pRoot]=qRoot;
    //        s[qRoot]+=s[pRoot];
    //    }
    //    else
    //    {
    //        a[qRoot]=pRoot;
    //        s[pRoot]+=s[qRoot];
    //    }
    //    //之后将根节点改变就相当于将该组的所有节点所在组都改论了
    //    coun--;//组数减少1
    //}
    //
    //int main()
    //{
    //    while(1)
    //    {
    //        int p,q;
    //        scanf("%d%d",&n,&m);
    //        coun=n;//初始时候每个节点都是一组
    //        for(int i = 0 ; i < n ; i++)
    //        {
    //            a[i]=i;s[i]=1;
    //        }
    //        for(int i = 0 ; i < m ; i++)
    //        {
    //            scanf("%d%d",&p,&q);//表示结点p和q连通
    //            unio(p,q);
    //        }
    //        int t = 4;
    //        while(t--)
    //        {
    //            scanf("%d%d",&p,&q);
    //            if(find(p)==find(q))printf("YES\n");
    //            else printf("NO\n");
    //        }
    //    }
    //    return 0;
    //}

例题hdu1232

城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

思路：最简单明显的并查集

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    #include <iomanip>
    #include <stack>
    using namespace std;
    
    const int maxn = 1005;
    int a[maxn];   //a[i]表示的是结点i的组号，初始值是
    int s[maxn];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
    int n,m,coun;  //count记录一共有多少组
    
    int Find(int p)
    {
         //一种更好的路径压缩
         //二分压缩路径（compresses paths by halving）：
         //具体思想就是把当前的结点，跳过一个指向父亲的父亲，
         //从而使整个路径减半深度减半。
         //这种办法比满路径压缩要快那么一点点。数据越大，当然区别就会越明显。
        while(p!=a[p])
        {
            a[p]=a[a[p]];
            //添加这样一行代码，将每个节点都挂在原父节点的
            //父节点上面，查找的时间复杂度至少少一半
            //路径压缩,在集合的查找过程中顺便将树的深度降低
            p=a[p];
        }
        return p;//查找p的组号(根节点)
    
    
        //满路径压缩（full compresses paths）：这是一种极其简单但又很常用的方法。
        //就是在添加另一个集合的时候，把所有遇到的结点都指向根节
    //    if(p!=a[p])
    //        a[p]=Find(a[p]);
    //    //在递归回来的时候把路径上元素的父亲指针都指向根结点。
    //    return a[p];
    
    }
    
    //一颗树要是连通并且没有环，最终的结果应该是结点的个数等于边的数目+1
    void Union(int p,int q)
    {
        int pRoot=Find(p);
        int qRoot=Find(q);//获得p和q的组号
        if(pRoot==qRoot) return ;   //此时说明这棵树有环
        //将小数作为大数的子树
        //按秩进行合并
        if(s[pRoot]<s[qRoot])
        {
            a[pRoot]=qRoot;
            s[qRoot]+=s[pRoot];
        }
        else
        {
            a[qRoot]=pRoot;
            s[pRoot]+=s[qRoot];
        }
        //之后将根节点改变就相当于将该组的所有节点所在组都改论了
        coun--;//组数减少1
    }
    
    int main()
    {
        while(scanf("%d",&n)!=EOF&&n)
        {
            scanf("%d",&m);
            int p,q;
            coun=n-1;//初始时候每个节点都是一组
            for(int i = 1 ; i <= n ; i++)
            {
                a[i]=i;s[i]=1;
            }
            for(int i = 0 ; i < m ; i++)
            {
                scanf("%d%d",&p,&q);//表示结点p和q连通
                Union(p,q);
            }
            printf("%d\n",coun);
        }
        return 0;
    }