并查集：检查网络 课程设计.docx
课程：算法与数据结构并查集建查网络课程设计数据结构与算法课程设计报告数据结构与算法课程设计报告错误!未定义书签.一、飕：并查集检直网络3L题目要求：32 .输入要求：33 .输出要求：3二、并查集操作41 .Creat()42 .find(inte)43 .hebin(intA,intB)4三、并查集的优化54 .路彳缩55 .启发式合并6四 .问题实现6五 .雌测试：10一,课题：并查集检查网络L题目要求：给定一个计算机网络以及机器间的双向连线列表,每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输。2 .输入要求：输入若干测试数据组成。对于每一组测试,第1行包含一个整数N(<10000)z即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为IClC2或者C或者CC1C2或者S,其中Cl和C2是两台计算机的序号J表示在Cl和C2间输入一条连线,C表示检查Cl和C2间是否可以传输文件,S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。3 .输出要求：对每一组C开头的测试，检查Cl和C2间是否可以传输文件，若可以，则在一行中输出"yes",否则输出当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件,则在一行中输出"Thenetworkisconnected."f否则输出"TherearekCOmPonents.",其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔二.并查集操作l.Creat()for(i=O;i<=n;i+)farheri=-1;2Jind(inte)每棵树表示一个集合,树的根作为集合的"代表元"。对于Find操作，实际上沿着父指针向上找到根即可。intFind(ints)(while(fathers!=s)s=fathers;returns;)这里用递归实现，每次查询的时间复杂度是树的深度，约为。(1)。3.hebin(intA,intB)对于hebin操作，分别找到A,B的代表元sizeA,sizeB,如果sizeA=sizeB,不进行任何操作。否则令parentB=A,或parentA=B,即可把两棵树合并。Voidhebin(intA,intB)intsi=find(u),s2=find(v);if(si!=s2)fasl=s2;return;)三、并查集的优化原理：在查找祖先时，找到后对路径上的所有节点，修改其父亲，使它直接连接根结点。正确性证明：设X所在集合的根结点为P,在Father(X)的路径上的某节点为y,当找到P=Father(X)后,因为途经y节点并且yp，所以必调用了Father(y)来找p,所以Father(y)必然为po当使fay=p后，Father(y)仍然是P,所以不会改变y点的基本属性，这种做法是可行的。1 .路径压缩寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find(X)都是O(PI)的复杂度，为减小这个复杂度用路径压缩，即当我们经过"递推"找到祖先节点后回溯”的时候!顺便将它的子孙节点都直接指向祖先，这样以后再次Find(X)时复杂度就变成O(I)了。intfind(inte)(if(e=parente)returne;parente=find(parente);returnparente;2 .启发式合并即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。voidhebi(intAzintB)(if(sizeA>=sizeB)(sizeA÷=sizeB;parentB=A;)else(sizeB+=sizeA;parentA=B;)四.问题实现#include<stdio.h>#defineMAX10001intparentMAX;intsizeMAX;初始化voidinit(intn)for(inti=1;i<=n;+i)(parenti=i;sizei=1;)voidhebin(intAJntB)元素少的集合合并到元素多的集合中,降低树的高度(if(sizeA>=sizeB)(sizeA+=sizeB;parentB=A;else(sizeB+=sizeA;parentA=B;intfind(inte)路径压缩if(e=parente)returne;parente=find(parente);returnparente;)intmain()(intn,count;intuzv,rl,r2;charoper;while(scanf("%d",&n)!=EOF)(if(n=0)break;init(n);while(scanf("%c",8ioper)!=EOF)(if(oper=,)(scanf("%d%d",&u,&v);rl=find(u);r2=find(v);if(rl!=r2)hebin(rl,r2);)elseif(oper=,C,)(scanf("%d%d",&u,&v);rl=find(u);r2=find(v);if(rl!=r2)printf("non");elseprintf("yesn");)elseif(oper=,S,)(count=0;for(inti=1;i<=n;+i)(if(i=parenti)count+;if(count=1)printf("Thenetworkisconnectednn");elseprintf("Thereare%dcomponentsnn",count);break;)return0;)五.数据测试：
