并查集 (Union-Find Sets)及其应用

并查集：(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有10的80次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。它支持以下三中种操作:
　　－Union (Root1, Root2) //并操作；把子集合Root2并入集合Root1中.要求：Root1和 Root2互不相交,否则不执行操作.
　　－Find (x) //搜索操作；搜索单元素x所在的集合,并返回该集合的名字.
　　－UFSets (s) //构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合.
　　－对于并查集来说，每个集合用一棵树表示。
　　－集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。
　　－设 S1= {0, 6, 7, 8 }，S2= { 1, 4, 9 }，S3= { 2, 3, 5 }

－为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。
　　－为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到 n-1。其中 n 是最大元素个数。在双亲表示中，第 i 个数组元素代表包含集合元素 i 的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息( ≥ 0 )，集合元素个数信息用负数表示。　　　

下标 parent

集合S1, S2和S3的双亲表示:

                  　　　        S1 ∪ S2的可能的表示方法

const int DefaultSize = 10;
　　class UFSets { //并查集的类定义
　　private:
　　　int *parent;
　　　int size;
　　public:
　　　UFSets ( int s = DefaultSize );
　　　~UFSets ( ) { delete [ ] parent; }
　　　UFSets & operator = ( UFSets const & Value );//集合赋值
　　　void Union ( int Root1, int Root2 );
　　　int Find ( int x );
　　　void UnionByHeight ( int Root1, int Root2 ); };
　　　UFSets::UFSets ( int s ) { //构造函数
　　　size = s;
　　　parent = new int [size+1];
　　　for ( int i = 0; i <= size; i++ ) parent[i] = -1;
　　}

　　unsigned int UFSets::Find ( int x ) { //搜索操作
　　　if ( parent[x] <= 0 ) return x;
　　　else return Find ( parent[x] );
　　}

　　void UFSets::Union ( int Root1, int Root2 ) { //并
　　　parent[Root2] = Root1; //Root2指向Root1
　　}

Find和Union操作性能不好。假设最初 n 个元素构成 n 棵树组成的森林，parent[i] = -1。做处理Union(0, 1), Union(1, 2), …, Union(n-2, n-1)后，将产生如图所示的退化的树。

                            

执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。若再执行Find(0), Find(1), …, Find(n-1), 若被
搜索的元素为i，完成Find(i)操作需要时间为O(i)，完成 n 次搜索需要的总时间将达到
　            　

Union操作的加权规则

　　为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以 i 为根的树中的结点个数少于以 j 为根的树中的结点个数，即parent[i] > parent[j]，则让 j 成为 i 的双亲，否则，让i成为j的双亲。此即Union的加权规则。

              parent[0](== -4) < parent[4] (== -3)

 

　　void UFSets::WeightedUnion(int Root1, int Root2) {
　　　//按Union的加权规则改进的算法
　　　int temp = parent[Root1] + parent[Root2];
　　　if ( parent[Root2] < parent[Root1] ) {
　　　　parent[Root1] = Root2; //Root2中结点数多
　　　　parent[Root2] = temp; 　//Root1指向Root2
　　　}
　　　else {
　　　　parent[Root2] = Root1; //Root1中结点数多
　　　　parent[Root1] = temp; 　//Root2指向Root1
　　　}
　　}

                           　使用加权规则得到的树

 

下面是几到用并查集可以方便解决的问题:

 

题目： 亲戚(Relations)

或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及.在这种情况下，最好的帮手就是计算机。

为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B en是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案。

参考输入输出格式 输入由两部分组成。

第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有两个数ai, bi，表示已知ai和bi是亲戚.

第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci, di，表示询问ci和di是否为亲戚。

对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No。

样例输入与输出

输入relation.in

10 7

2 4

5 7

1 3

8 9

1 2

5 6

2 3

3

3 4

7 10

8 9

输出relation.out

Yes

No

Yes

如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超时。

例程:

 

#include<iostream>

using namespace std;

int N,M,Q;

int pre[20000],rank[20000];

void makeset(int x)

 {

     pre[x]=-1;

     rank[x]=0;

 }

int find(int x)

 {

     int r=x;

     while(pre[r]!=-1)

      r=pre[r];

     while(x!=r)

      {

          int q=pre[x];

          pre[x]=r;

          x=q;

      }

    return r;      

 }    

void unionone(int a,int b)

 {

     int t1=find(a);

     int t2=find(b);

     if(rank[t1]>rank[t2])

       pre[t2]=t1;

    else

       pre[t1]=t2;

    if(rank[t1]==rank[t2])

      rank[t2]++;     

 }       

int main()

 

{

   int i,a,b,c,d;

    while(cin>>N>>M)

     {

         for(i=1;i<=N;i++)

          makeset(i);

        for(i=1;i<=M;i++)

          {

              cin>>a>>b;

              if(find(a)!=find(b))

               unionone(a,b);

          }

        cin>>Q; 

        for(i=1;i<=Q;i++)

         {

             cin>>c>>d;

             if(find(c)==find(d))

              cout<<"YES"<<endl;

             else

              cout<<"NO"<<endl; 

         }           

     }   

    return 0;

}

 

ZJU1789The Suspects

【问题描述】

 

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.

In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).

Once a member in a group is a suspect, all members in the group are suspects.

However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

Input

The input contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n-1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.

A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.

Output

For each case, output the number of suspects in one line.

Sample Input

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Sample Output

4
1
1

【算法分析】

 

这道题的意思很简单,n个人编号,从0到n-1,这n个人分成m个集合(1个人可以参加不同的集合),求的就是最后所有和0号有关系的集合的

人数.

如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超时.我们在题目给出的每个集合的人员编号时,进行并查

操作,不过在进行合并操作时,合并的是两个集合的元素个数.最后0号元素所在的集合数目就是所求.

例程:

#include<iostream>

#include<cstdio>

using namespace std;

const int size=30000;

int pre[size],num[size];

int n,m,k;

void makeset(int x)

 {

     pre[x]=-1;

     num[x]=1;

 }

int find(int x)//非递归压缩路径

 {

     int r=x;

     while(pre[r]!=-1)

      r=pre[r];

     while(x!=r)

      {

          int q=pre[x];

          pre[x]=r;

          x=q;

      }

    return r;      

 }    

int unionone(int a,int b)

{

    int t1,t2;

    t1=find(a);

    t2=find(b);

    if(t1==t2) return 0;

    if(num[t2]<=num[t1])

    {

        pre[t2]=t1;

        num[t1]+=num[t2];

    }

    else

    {

        pre[t1]=t2;

        num[t2]+=num[t1];

    }

    return 0;

}

int main()

 {  

     freopen("in.txt","r",stdin);

     freopen("out.txt","w",stdout);

     int i,j,a,b;

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

      {

          if(n==0&&m==0)

           break;

          for(i=0;i<n;i++)

            makeset(i);

          for(i=0;i<m;i++)

           {

               //cin>>k;

               scanf("%d",&k);

               if(k==0) continue;

               //cin>>a;

                scanf("%d",&a);

                a=find(a);

               for(j=1;j<k;j++)

                {

                    //cin>>b;

                    scanf("%d",&b);

                    b=find(b);

                    unionone(a,b);

                }   

           }

         printf("%d\n",num[find(0)]);      

      }   

     return 0;

 }    

 

  

   

    

     

       

 

 

银河英雄传说

 

【问题描述】

        公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

        宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

        杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

        然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

        在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

        作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

        最终的决战已经展开，银河的历史又翻过了一页……

 

【输入文件】

输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。

以下有T行，每行有一条指令。指令有两种格式：

1.        M  i  j  ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。

2.        C  i  j  ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

 

【输出文件】

输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：

如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

　如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

 

【样例输入】

4

M 2 3

C 1 2

M 2 4

C 4 2

 

【样例输出】

-1

1

 

【样例说明】

战舰位置图：表格中阿拉伯数字表示战舰编号

	第一列	第二列	第三列	第四列	……
初始时	1	2	3	4	……
M 2 3	1		3 2	4	……
C 1 2	1号战舰与2号战舰不在同一列，因此输出-1
M 2 4	1			4 3 2	……
C 4 2	4号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1

 

【算法分析】

        同一列的战舰组成一个并查集,在集合中,我们以当前列的第一艘战舰作为集合的代表元.并查集的数据类型采用树型,树的根结点即为集合的代表元.为了查询的效率达到最优,我们进行了路径压缩的优化:首先找到树根,然后将路径上所有结点的父结点改为根,使得树的深度为1.

        问题是,题目不仅要求判别两个结点是否在同一个集合(即两艘战舰是否在同一列),而且还要求计算结点在有序集合的位置(即每一艘战舰相隔列的第一艘战舰几个位置),       我们增加了一个数组behind[x],记录战舰x在例中的相对位置.

        查找一个元素x所在集合的代表元时，先从x沿着父亲节点找到这个集合的代表元root，然后再从x开始一次到root的遍历，累计其间经过的每一个子结点的behind值,其和即为behind[i].,如下图所示:

          

       按照题意,合并指令Mxy,含义是让战舰x 所在的整个战舰队列,作为一个整体(头在前,尾在后)接至战舰y所在的战舰队列的尾部,显然两个队列合并成同一列后,其集合代表元为结点y所在的树的根结点fy,x所在的树的根结点fx,合并后,fx的相对位置为合并前y所在集合的结点数, behind[fx]=num[fy],新集合的结点数为原来两个集合结点数的和 num[fy]+=num[fx]. 则如果战舰x和战舰y在同一列,则他们相隔

|behind[x]-behind[y]|-1艘战舰.如下图:

 

例程:

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int size=30001;

int pre[size],num[size],behind[size];//behind[x]战舰x在列中的相对位置

int n,m,k;

void makeset(int x)

 {

     pre[x]=-1;

     num[x]=1;

 }

int find(int x)//查找结点x所在树的根结点,并对该树进行路径压缩

 {

     int r=x;

     int j;

     while(pre[r]!=-1)//找出结点x所在树的根结点r

      r=pre[r];

     while(x!=r)

      {

          int q=pre[x];//路径压缩

          pre[x]=r;

          j=q;

          do{//迭代求出路径上每一个子结点相对于r的相对位置

              behind[x]+=behind[j];

              j=pre[j];

            }while (j!=-1);   

          x=q;

      }

    return r;      

 }    

void MoveShip(int a,int b)

{

    int t1,t2;

    t1=find(a);//计算a所在树的根结点t1

    t2=find(b);//计算b所在树的根结点t2

    pre[t1]=t2;//将t1的父结点设为t2

    behind[t1]=num[t2];//计算t1的相对位置为num[t2]

    num[t2]+=num[t1]; //计算新集合的结点数

 

}

 

void CheckShip(int x,int y)

 {

     int f1,f2;

     f1=find(x);

     f2=find(y);

     if(f1!=f2)

      cout<<-1<<endl;

     else

      cout<<abs(behind[x]-behind[y])-1<<endl;

 }

int main()

 {

   freopen("galaxy.in","r",stdin);

    freopen("out.txt","w",stdout);

 

     int n,x,y;

     char ch;

     while(cin>>n)

      {

          for(int i=1;i<size;i++)

           {

               makeset(i);

           }

          memset(behind,0,sizeof(behind));   

          while(n--)

           {

               cin>>ch>>x>>y;

               if(ch=='M')

                 MoveShip(x,y); //处理合并指令

               else if(ch=='C')

                 CheckShip(x,y);  //处理询问指令

           }   

      } 

   return 0;    

 }