并查集：检查网络 课程设计.docx

《并查集：检查网络 课程设计.docx》由会员分享，可在线阅读，更多相关《并查集：检查网络 课程设计.docx（11页珍藏版）》请在第一文库网上搜索。

1、课程：算法与数据结构并查集T植查网纣课程设计数据结构与算法课程设计报告数据结构与算法课程设计报告错误!未定义书签。一、课题：并查集检查网络31 .题目要求：32 .输入要求：33 .输出要求：3二、并查集操作41 .Creat()42 .find(inte)43 .hebin(intA,intB)4三、并查集的优化51 .路径压缩52 .启发式合并6四 .问题实现6五 .数据测试：10一.课题：并查集检查网络1 .题目要求：给定一个计算机网络以及机器间的双向连线列表,每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定

2、两台计算机，它们之间是否可以进行文件传输。2 .输入要求：输入若干测试数据组成。对于每一组测试,第1行包含一个整数N(IOOOO)z即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为IC1C2或者C或者CC1C2或者S,其中C1和C2是两台计算机的序号J表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为。时，表示全部测试结束，不要对该数据做任何处理。3 .输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出yes，否则输出no。当读到S时，检查整个网络。若网络中任意两机

3、器间都可以传输文件,则在一行中输出nThenetworkisconnected.z否则输出nTherearekcomponents.,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔二、并查集操作1.Creat()for(i=O;i=sizeB)(sizeA+=sizeB;parentB=A;)e1se(sizeB+=sizeA;parentA=B;)四.问题实现#inc1ude#defineMAX10001intparentMAX;intsizeMAX;初始化voidinit(intn)for(inti=1;i=sizeB)(sizeA+=sizeB;paretB=A;)e1se

4、(sizeB+=sizeA;parentA=B;)intfind(inte)路径压缩if(e=parente)returne;parente=find(parete);returnparente;)intmain()(intn,count;intuzvzr1zr2;charoper;whi1e(scanf(,%d,z&n)!=EOF)(if(n=0)break;init(n);whi1e(scanf(,%c,z&oper)!=EOF)(if(oper=,)(scanf(,%d%c,&u,&v);r1=find(u);r2=find(v);if(r1!=r2)hebin(r1zr2);)e1seif(oper=C,)(scanf(,%d%d,11&u,&v);r1=find(u);r2=find(v);if(r1!=r2)printf(non);e1sepntf(,yesn);)e1seif(oper=,S,)(count=0;for(inti=1;i=n;+i)(if(i=parenti)count+;)if(count=1)printf(,Thenetworkisconnectednn);e1seprintf(,Thereare%dcomponentsnn,zcount);break;)return0;)五.数据测试: