ACM--ICPC--重要补充知识

1、在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（13秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构并查集来描述。什么是并查集？并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在

2、使用中以森林来表示。集就是让每个元素构成一个单元素的集合，并就是按一定顺序将属于同一组的元素所在的集合合并。编辑本段并查集的主要操作：初始化把每个点所在集合初始化为其自身查找查找元素所在的集合即根节点合并将两个元素所在的集合合并为一个集合合并两个不相交集合判断两个元素是否属于同一集合辅助例题亲戚(Relations)题目描述： 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 输入格式 Input F

3、ormat 第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。 输出格式 Output Format P行，每行一个Yes或No。表示第i个询问的答案为“具有”或“不具有”亲戚关系。varfather:array1.5000of integer;i,j,k,p,n,m:integer;Function getfather(v:intege

4、r):integer;beginif fatherv=v then exit(v);fatherv:=getfather(fatherv);getfather:=fatherv;end;Procedure merge(x,y:integer);beginx:=getfather(x);y:=getfather(y);fatherx:=y;end;Function judge(x,y:integer):boolean;beginx:=getfather(x);y:=getfather(y);If x=y then exit(true) else exit(false);end;beginread

5、ln(n,m,p);for i:=1 to n do fatheri:=i;预处理for i:=1 to m dobeginread(j,k);merge(j,k);end;for i:=1 to p dobeginread(j,k);if judge(j,k) then writeln('Yes') else writeln('No');end;end.编辑本段思路点拨一 问题实质初步分析觉得本题是一个图论中判断两个点是否在同一个连通子图中的问题。对于题目中的样例，以人为点，关系为边，建立无向图如下：图0-0-1 请补充图解比如判断3和4是否为亲戚时，我们检查

6、3和4是否在同一个连通子图中，结果是，于是他们是亲戚。又如7和10不在同一个连通子图中，所以他们不是亲戚。用图的数据结构的最大问题是，我们无法存下多至(M=)2 000 000条边的图，后面关于算法时效等诸多问题就免谈了。用图表示关系过于“奢侈”了。其实本题只是一个对分离集合（并查集）操作的问题。我们可以给每个人建立一个集合，集合的元素值有他自己，表示最开始时他不知道任何人是它的亲戚。以后每次给出一个亲戚关系a, b，则a和他的亲戚与b和他的亲戚就互为亲戚了，将a所在集合与b所在集合合并。对于样例数据的操作全过程如下：输入关系 分离集合初始状态(2,4) 2,4(5,7) 2,4 5,7(1,

7、3) 1,3 2,4 5,7(8,9) 1,3 2,4 5,7 8,9(1,2) 1,2,3,4 5,7 8,9(5,6) 1,2,3,4 5,6,7 8,9(2,3) 1,2,3,4 5,6,7 8,9最后我们得到4个集合1,2,3,4, 5,6,7, 8,9, ，于是判断两个人是否亲戚的问题就变成判断两个数是否在同一个集合中的问题。如此一来，需要的数据结构就没有图结构那样庞大了。算法需要以下几个子过程：(1) 开始时，为每个人建立一个集合SUB-Make-Set(x)；(2) 得到一个关系后a,b，合并相应集合SUB-Union(a,b)；(3) 此外我们还需要判断两个人是否在同一个集合中

8、，这就涉及到如何标识集合的问题。我们可以在每个集合中选一个代表标识集合，因此我们需要一个子过程给出每个集合的代表元SUB-Find-Set(a)。于是判断两个人是否在同一个集合中，即两个人是否为亲戚，等价于判断SUB-Find-Set(a)=SUB-Find-Set(b)。有了以上子过程的支持，我们就有如下算法。PROBLEM-Relations(N, M, a1,aM, b1,bM, Q, c1,cQ, d1,dQ)1 for i1 to N2 do SUB-Make-Set(i)3 for i1 to M4 do if SUB-Find-Set(ai)?SUB-Find-Set(bi)5

9、then SUB-Union(ai, bi)6 for i1 to Q7 do if SUB-Find-Set(ci)=SUB-Find-Set(di)8 then output “Yes?”9 else output “No?”解决问题的关键便为选择合适的数据结构实现分离集合的操作，使算法的实现效率最高。二 单链表实现一个节点对应一个人，在同一个集合中的节点串成一条链表就得到了单链表的实现。在集合中我们以单链表的第一个节点作为集合的代表元。于是每个节点x（x也是人的编号）应包含这些信息：指向代表元即表首的指针headx，指向表尾的指针tailx，下一个节点的指针nextx。SUB-Make-

10、Set(x)过程设计如下：SUB-Make-Set(x)10 headxx11 tailxx12 nextxNIL求代表元的SUB-Find-Set(x)过程设计如下：SUB-Find-Set(x)13 return headx前两个过程比较简单，SUB-Union(a,b)稍微复杂一点。我们要做的是将b所在链表加到a所在链表尾，然后b所在链表中的所有节点的代表元指针改指a所在链表的表首节点，如图所示。图0-0-2过程的伪代码如下：SUB-Union(a,b)14 nexttailheadahead15 tailheadatailhead16 phead17 while p?NIL18 do

11、headpheada19 pnextp现在我们来分析一下算法的时间效率。SUB-Make-Set(x)和SUB-Find-Set(x)都只需要O(1)的时间，而SUB-Union(a,b)的时间效率与b所在链表的长度成线性关系。最坏情况下，即有操作序列SUB-Union(N-1,N), SUB-Union(N-2,N-1), , SUB-Union(1,2)时，整个算法PROBLEM-Relations的时间复杂度为O(N+M+N2+Q)=O(N2+M+Q)。由于算法的时间复杂度中O(M+Q)是必需的，因此我们要让算法更快，就要考虑如何使减小O(N2)。我们想到合并链表时，我们可以用一种启发式

12、的方法：将较短的表合并到较长表上。为此每个节点中还需包含表的长度的信息。这比较容易实现，我们就不写出伪代码了。我们来分析一下现在SUB-Union(a,b)的时间复杂度。首先我们给出一个固定对象x的代表元指针headx被更新次数的上界。由于每次x的代表元指针被更新时，x必然在较小的集合中，因此x的代表元指针被更新一次后，集合至少含2个元素。类似地，下一次更新后，集合至少含4个元素，继续下去，当x的代表元指针被更新 ?log k? 次后，集合至少含k个元素，而集合最多含n个元素，所以x的代表元指针至多被更新 ?log n? 次。所以M次SUB-Union(a,b)操作的时间复杂度为O(NlogN

13、+M)。算法总的时间复杂度为O(N log N + M + Q)。三 分离集合的森林分离集合的另一种更快的实现是用有根树来表示集合：每棵树表示一个集合，树中的节点对应一个人。图示出了一个分离集合的森林。图0-0-3每个节点x包含这些信息：父节点指针px，树的深度rankx。其中rankx将用于启发式合并过程。于是建立集合过程的时间复杂度依然为O(1)。SUB-Make-Set(x)20 pxx21 rankx0用森林的数据结构来实现的最大好处就是降低SUB-Union(a,b)过程的时间复杂度。SUB-Union(a,b)22 SUB-Link(SUB-Find-Set(a),SUB-Find

14、-Set(b)SUB-Link(a,b)23 pab合并集合的工作只是将a所在树的根节点的父节点改为b所在树的根节点。这个操作只需O(1)的时间。而SUB-Union(a,b)的时间效率决定于SUB-Find-Set(x)的快慢。SUB-Find-Set(x)24 if x=px25 then return x26 else return SUB-Find-Set(px)这个过程的时效与树的深度成线性关系，因此其平均时间复杂度为O(logN)，但在最坏情况下（树退化成链表），时间复杂度为O(N)。于是PROBLEM-Relations最坏情况的时间复杂度为O(N(M+Q)。有必要对算法进行优化

15、。第一个优化是启发式合并。在优化单链表时，我们将较短的表链到较长的表尾，在这里我们可以用同样的方法，将深度较小的树指到深度较大的树的根上。这样可以防止树的退化，最坏情况不会出现。SUB-Find-Set(x)的时间复杂度为O(log N)，PROBLEM-Relations时间复杂度为O(N + logN (M+Q)。SUB-Link(a,b)作相应改动。SUB-Link(a,b)27 if ranka>rank28 then pa29 else pab30 if ranka=rank31 then rankrank+1然而算法的耗时主要还是花在SUB-Find-Set(x)上。第二个优

16、化是路径压缩。它非常简单而有效。如图所示，在SUB-Find-Set(1)时，我们“顺便”将节点1, 2, 3的父节点权改为节点4，以后再调用SUB-Find-Set(1)时就只需O(1)的时间。图0-0-4于是SUB-Find-Set(x)的代码改为：SUB-Find-Set(x)32 if x?px33 then pxSUB-Find-Set(px)34 return px该过程首先找到树的根，然后将路径上的所有节点的父节点改为这个根。实现时，递归的程序有许多栈的操作，改成非递归会更快些。SUB-Find-Set(x)35 rx36 while r?pr37 do rpr38 while

17、x?r39 do qpx40 pxr41 xq42 return r改进后的算法时间复杂度的分析十分复杂，如果完整的写出来足可写一节，这里我们指给出结论：改进后的PROBLEM-Relations其时间复杂度为O(N+(M+Q)?(M+Q,N)，其中?(M+Q,N)为Ackerman函数的增长极为缓慢的逆函数。你不必了解与Ackerman函数相关的内容，只需知道在任何可想象得到的分离集合数据结构的应用中，?(M+Q,N) ? 4，因此PROBLEM-Relations的时间复杂度可认为是线性的O(N+M+Q)。解(略)编辑本段总述本题的输入数据量很大，这使得我们的程序会在输入中花去不少时间。如

18、果你用Pascal写程序，可以用库函数SetTextBuf为输入文件设置缓冲区，这可以使输入过程加快不少。如果你是用C语言的话，就不必为此操心了，系统会自动分配缓冲区。并查集学习小节(POJ版) 什么是并查集呢，我相信大家都已经很熟悉了，在这里我就不再赘述。写这篇文章的主要目的不是新手教学，而是为了借POJ上相关的题目，全面的总结一下并查集问题和它的各个变种。POJ 1611 The Suspects题目大意:有n个学生（标号为0 to n-1),m个学生社团，给出每个社团里所有学生的标号，并假设0号学生患有SARS（社团里只要用一个学生患病，则整个社团里的学生都会被隔离），问最后一共会有多少

19、学生被隔离？这是一个最基础的并查集的应用，扫描每一个社团，只要两个学生出现在同一个社团，则将这两个集合合并起来，最后输出0号点所在集合的rank值集合（rank值记录这个集合中的元素个数并用一个flag值跟踪0号元素所在集合标号）即可。这是并查集问题的第一种应用：集合合并，判断两点是不是在同一个集合，求某一个集合上的元素个数等。#include<stdio.h>#define MAX 30000int fMAX;/这里的1001只是一个示意性的数字 代表初始状态下的分支数目int rMAX;int flag;/由于不知道应

20、该将子树挂到那个集合上面去，故需要一个准则，这里的准则是将子树挂到/r值大的集合上面去,初始状态下r数组的值均为一，代表每个分支下只有一个数字int find(int n)    if(fn=n)        return n;    else        fn=find(fn);   

21、0;return fn;/查找函数，并压缩路径int Union(int x,int y)    int a=find(x);    int b=find(y);    if(a=b)        return 0;    else if(ra<=rb) 

22、60;          fa=b;        rb+=ra;        if(a=flag)            flag=b;      

23、0; else            fb=a;        ra+=rb;        if(b=flag)            flag=a;   &

24、#160;    return 1;    /合并函数，如果属于同一分支则返回0，成功合并返回1int main()    int n,m;    int i,j;    int num;    int maxnum=0;    while(scanf(&qu

25、ot;%d%d",&n,&m)            flag=0;        maxnum=0;        int temp1,temp2;        if(n=0&&m=0

26、)            break;        for(i=0;i<n;i+)                    fi=i;     

27、       ri=1;                for(j=1;j<=m;j+)                    scanf("%d&quo

28、t;,&num);            for(i=0;i<num;i+)                            if(i=0)   &#

29、160;                scanf("%d",&temp1);                else           &

30、#160;                        scanf("%d",&temp2);                   

31、0;Union(temp1,temp2);                                            printf("%d

32、n",rflag);                return 0;HDOJ1213 How many tables?#include<algorithm> #include<iostream> #include<cstring> #define MAX 30000 using namespace std; int fMAX; int rMAX; int flag; int fi

33、nd(int n) if(fn!=n) fn=find(fn); return fn; int Union(int x,int y) int a=find(x); int b=find(y); if(a=b) return 0; else fa=b; return 1; int main() int n,m; int i,j; int num,N; int maxnum=0;scanf("%d",&N); while(N!=0) N-; scanf("%d%d",&n,&m); int temp1,temp2; for(i=1;i

34、<=n;i+) fi=i; ri=1; for(j=1;j<=m;j+) cin>>temp1>>temp2; Union(temp1,temp2); int sum=0; for(j=1;j<=n;j+) if(fj=j) sum+; cout<<sum<<endl; system("pause");return 0; POJ 2492 A Bug's Life个人认为它是初级并查集问题的一个升级。同时这个题让我看到了食物链的影子。题目的大意是给出n只bug和m次观察到的性行为，并以此为依据判断两只

35、bugs是不是有同性恋行为(gay)。比如3只bug1 2有性行为2 3有性行为1 3有性行为->>>>>首先1,2是异性。->>>>>然后2,3是异性。可以推出1,3是异性。但是1，3有性行为，所以可以判断出有一定有同性恋。剥离这个题目所赋予的外壳，我们抽出这个问题的本质：并查集！其实，这里最重要的是去维护每一个点到集合顶点的偏移量。（注意：下面生造了一个词 所谓集合元素 比如说fi=i,那么i就是集合元素，集合偏移量就是集合元素的偏移量）初始状态下，应该是 i号点挂在i号集合下面我们考虑一般情况：假设合并的过程已经进行了一部分 ，

36、这样每一个集合下面都有元素，且各自对于顶点的偏移量都算出来了；现在在a集合中的元素x和b集合中的元素y进行合并。此时有两中情况改变偏移量；1.首先是集合的合并，如果要将a,b集合合并，又要保证x,y数字的kind不相同，比如说把b集合挂到a集合下面去。代表集合的那个元素，他的偏移量永远是0，所以b要改变偏移量，使得b里面的y在进行变换后要和x相异。如果 kindx=0;kindy=0;那么y对应的那个代表集合的元素的偏移量必须变成1，因为只有这样才能使得合并后，x,y有不同的kind;如果 kindx=0,kindy=1;y对应代表集合的元素偏移量是0，所以对应集合偏移量还是0；类推 

37、;  kindx=1,kindy=0,同上,0；           kindx=1,kindy=1,y集合偏移量应该变为1；综上 可以得到一个同或的关系。用等式 kinda=(kindx+kindy+1)%2;恰好满足要求.2.然后是压缩路径时候的偏移量改变个人认为，这个主要是解决集合合并时候产生的“残余问题”，因为在合并集合的时候只是考虑了集合的偏移量，至于它下面的元素一概不管。一个压缩路径既分离了父子元素的偏移量，又使得子元素直接指向集合元素。总而言

38、之，并查集的操作就是不断地维护者各个集合中，每个元素身上对集合元素的偏移关系。从而确定他们是否具有同性恋。在这个题中，假设是不存在同性恋的，所以只有找到矛盾才输出 有同性恋。#include<iostream>#include<cstdio>using namespace std;#define MAX 2001int fMAX;int kindMAX;int n,m;int testcase;void init()    int 

39、i;    for(i=1;i<=n;i+)             fi=i;        kindi=0;    int Find(int n)    if(fn=n)      

40、;  return n;    int t=Find(fn);    kindn=(kindn+kindfn)%2;    fn=t;    return fn;int  Union(int x,int y)    int a=Find(x);    int&

41、#160;b=Find(y);    if(a=b)            if(kindx=kindy)            return 1;/1代表有同性恋情况        else   &

42、#160;         fa=b;        kinda=(kindx+kindy+1)%2;        return 0;int main()    scanf("%d",&testcase);    int

43、 i,j;    int a,b;    int flag;    for(i=1;i<=testcase;i+)            flag=0;        scanf("%d%d",&n,&m);

44、        init();        for(j=1;j<=m;j+)                    scanf("%d%d",&a,&b);   &#

45、160;        if(Union(a,b)                            flag=1;          

46、                  if(flag=1)            printf("Scenario #%d:nSuspicious bugs found!nn",i);     

47、0;  else             printf("Scenario #%d:nNo suspicious bugs found!nn",i);        return 0;POJ 1182 食物链 中文题，让你输出假话的个数。其实这道题是上一道题的扩展，如果把上一道题

48、也想成是食物链的话，就是1吃2，2吃1.而这里是三个动物，所以同样是维护一个偏移量，只不过多了一位罢了。程序的过程实质上就是在维护并查集，判断是否是假话是在维护的过程中进行的，只能算是附属品吧。#include<iostream>using namespace std;#define MAX 50005int fMAX;int kindMAX;int n,m;void init()    int i;    for

49、(i=1;i<=n;i+)             fi=i;        kindi=0;    int Find(int n)        if(fn=n)      

50、0; return n;    int t=Find(fn);    kindn=(kindn+kindfn)%3;    fn=t;    return fn;bool  Union(int x,int y,int c)    if(x>n|y>n)    

51、;    return 1;    int a=Find(x);    int b=Find(y);    if(c=1)            if(a=b)           

52、;         if(kindx!=kindy)                return true;                else if(a!=b)&#

53、160;                   fb=a;            kindb=(kindx-kindy+3)%3;             

54、60;  else            if(x=y)            return true;        if(a=b)         

55、0;          if(kindx+1)%3!=kindy)                return true;                else

56、0;if(a!=b)                    fb=a;            kindb=(kindx-kindy+4)%3;           

57、60;    return false;int main()    int i,j;    int a,b,c;    int sum=0;    scanf("%d%d",&n,&m);    init();    for(i=1;

58、i<=m;i+)            scanf("%d%d%d",&c,&a,&b);        if(Union(a,b,c)            sum+;     

59、   printf("%dn",sum);    return 0; 这里将两个集合并起来并将所挂集合偏移量指向：kindb=(kindx-kindy+4)%3;想想上一题是不是也很类似呢其实上一题的公式也可以改成kindb=(kindx-kindy+3)%2; 不管是几个动物循环，都能得到类似的结论，所以以后碰到4，5，6，7。个动物的食物链，你应该也会做了吧？_POJ 1988 Cube Stacking这道题更有意思了，说它开辟了并查集问题的新局面并不为过；上面2道题，研究的主要

60、是到集合元素的偏移量，而这道题要求的是一个“逻辑上”到达集合元素的距离！集合合并的时候同样只修改被挂集合元素的距离值，残余部分留给压缩路径来处理.如果理解了上面的问题，这个问题就很好理解了。#include<iostream>#include<algorithm>#include<cmath>using namespace std;#define MAX 30000int fMAX+1;int rMAX+1;int aboveMAX+1;void init() 

61、0;  int i;    for(i=1;i<=MAX;i+)            abovei=0;        fi=i;        ri=1;    int realfather;int find(int n)    int t;    if(fn=n)            realfather=n;