2010年8月16日并查集的应用

1并查集(Union-FindSets)及其应用并查集：(union-findsets)是一种简单的用途广泛的集合.并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(MAlpha(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)，集合元素个数信息用负数表示。S1∪S2的可能的表示方法:voidufsets(ints){//构造函数inti,parent[s];for(i=0;is;i++){2parent[i]=-1;}}intfind(intx)//搜索操作{if(parent[x]=0){returnx;}else{returnfind(parent[x]);}voidunion(introot1,introot2){//合并操作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的加权规则。3parent[0](==-4)parent[4](==-3)voidWeightedUnion(intRoot1,intRoot2){//按Union的加权规则改进的算法inttemp=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)或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及.在这种情况下，最好的帮手就是计算机。4为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，你可以推出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≤1000000)，每行为ci,di，表示询问ci和di是否为亲戚。对于每个询问ci,di，若ci和di为亲戚，则输出Yes，否则输出No。样例输入与输出输入relation.in1072457138912562333471089输出relation.outYesNoYes如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超时。例程:#includestdio.hintn,m,q;intpre[20000],rank[20000];voidmakeset(intx){pre[x]=-1;rank[x]=1;}voidunionone(inta,intb){introot1=find(a);introot2=find(b);if(rank[root1]rank[root2]){pre[root2]=root1;rank[root1]++;}5else{pre[root1]=root2;rank[root2]++;}}intfind(intx){intr=x,q;while(pre[r]!=-1){r=pre[r];}returnr;}intmain(intargc,char**argv){inta,b,c,d,i;scanf(%d,&n);getchar();scanf(%d,&m);getchar();for(i=0;in;i++){makeset(i);}for(i=0;im;i++){scanf(%d%d,&a,&b);getchar();if(find(a)!=find(b)){unionone(a,b);}}scanf(%d,&q);getchar();for(i=0;iq;i++){scanf(%d%d,&c,&d);getchar();if(find(c)==find(d)){printf(YES\n);}else{printf(NO\n);}6}return0;}题目二：利用并查集实现最小生成树：输入数据:11AB7AD5BC8BD9BE7CE5DE15DF6EF8EG9FG11输出:A-D:5C-E:5D-F:6A-B:7B-E:7E-G:9Total:39#includestdio.h#includestdlib.h#defineMAX100/*定义边(x,y)，权为w*/typedefstruct7{intx,y;intw;}edge;edgee[MAX];/*rank[x]表示x的秩*/intrank[MAX];/*father[x]表示x的父节点*/intfather[MAX];intsum;/*比较函数，按权值(相同则按x坐标)非降序排序*/intcmp(constvoid*a,constvoid*b){if((*(edge*)a).w==(*(edge*)b).w){return(*(edge*)a).x-(*(edge*)b).x;}return(*(edge*)a).w-(*(edge*)b).w;}/*初始化集合*/voidMake_Set(intx){father[x]=x;rank[x]=0;}/*查找x元素所在的集合,回溯时压缩路径*/intFind_Set(intx){if(x!=father[x]){father[x]=Find_Set(father[x]);}returnfather[x];}/*合并x,y所在的集合*/voidUnion(intx,inty,intw){if(x==y)return;/*将秩较小的树连接到秩较大的树后*/if(rank[x]rank[y])8{father[y]=x;}else{if(rank[x]==rank[y]){rank[y]++;}father[x]=y;}sum+=w;}/*主函数*/intmain(){inti,n;intx,y;charchx,chy;/*读取边的数目*/scanf(%d,&n);getchar();/*读取边信息并初始化集合*/for(i=0;in;i++){scanf(%c%c%d,&chx,&chy,&e[i].w);getchar();e[i].x=chx-'A';e[i].y=chy-'A';Make_Set(i);}/*将边排序*/qsort(e,n,sizeof(edge),cmp);sum=0;for(i=0;in;i++){x=Find_Set(e[i].x);y=Find_Set(e[i].y);if(x!=y){9printf(%c-%c:%d\n,e[i].x+'A',e[i].y+'A',e[i].w);Union(x,y,e[i].w);}}printf(Total:%d\n,sum);system(pause);return0;}题目三：食物链动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是1XY，表示X和Y是同类。第二种说法是2XY，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1）当前的话与前面的某些真的话冲突，就是假话；2）当前的话中X或Y比N大，就是假话；3）当前的话表示X吃X，就是假话。你的任务是根据给定的N（1=N=50,000）和K句话（0=K=100,000），输出假话的总数。Input第一行是两个整数N和K，以一个空格分隔。以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。若D=1，则表示X和Y是同类。若D=2，则表示X吃Y。Output只有一个整数，表示假话的数目。SampleInput100711011212223233113231155SampleOutput3#includestdio.h/*father[x]表示x的根节点*/intfather[50005];/*rank[x]表示father[x]与x的关系rank[x]==0表示father[x]与x是同类10rank[x]==1表示x吃father[x]rank[x]==2表示father[x]吃x*/intrank[50005];/*初始化集合*/voidMake_Set(intx){father[x]=x;}/*查找x所在的集合*/intFind_Set(intx){intt;if(father[x]==x)returnx;t=father[x];father[x]=Find_Set(father[x]);/*因为压缩时根节点改变，必须更新father[x]与x的关系*/rank[x]=(rank[t]+rank[x])%3;returnfather[x];}/*合并a和b*/voidUnion_Set(inta,intb,intlen){intra=Find_Se