題目大意：將多個(gè)電腦通過網(wǎng)線連接起來，不斷查詢2臺(tái)電腦之間是否連通。

問題來源：中國大學(xué)mooc

05-樹8?File Transfer?（25 分）

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:

Each input file contains one test case. For each test case, the first line contains?N?(2≤N≤10?4??), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and?N. Then in the following lines, the input is given in the format:

I c1 c2

where?I?stands for inputting a connection between?c1?and?c2; or

C c1 c2

where?C?stands for checking if it is possible to transfer files between?c1?and?c2; or

S

where?S?stands for stopping this case.

Output Specification:

For each?C?case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between?c1?and?c2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are?kcomponents." where?k?is the number of connected components in this network.

Sample Input 1:

5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 S

Sample Output 1:

no no yes There are 2 components.

Sample Input 2:

5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 I 1 3 C 1 5 S

Sample Output 2:

no no yes yes The network is connected.

?

思路： 并查集的題目，首先知道如何表示并查集的數(shù)據(jù)結(jié)構(gòu)：

typedef struct{ int data; int parent; }SetType[MaxSize]; 本題可以進(jìn)行優(yōu)化：只用一個(gè)數(shù)組? int SetType[MaxSize]表示即可，數(shù)組下標(biāo)表示計(jì)算機(jī)的序號(hào)，SetType[index]表示為他的父節(jié)點(diǎn)，就是連通節(jié)點(diǎn)的序號(hào)。 并查集的Find? 和union函數(shù)如下： int Find(SetType S[],int x){int i;for(i=0;i<MaxSize&&S[i].data!=x;i++); //查找的時(shí)間復(fù)雜度nif(i>MaxSize)return -1;for(;S[i].parent>=0;i=S[i].parent);return i; //找到X所屬集合，返回樹根結(jié)點(diǎn)在數(shù)組S中的下標(biāo) }void Union(SetType S[],int x1,int x2){int root1,root2;root1=find(S,x1);root2=find(S,x2);if(root1!=root2)S[root2]=root1;}

優(yōu)化后的Find和路徑壓縮函數(shù)如下：

#define Maxitem 10000int S[Maxitem]; //采用路徑壓縮，尾遞歸尋找他的根結(jié)點(diǎn) int find(int x){if(S[x]<0)return x;////先找到根； 把根變成 X 的父結(jié)點(diǎn)； 再返回根。else return S[x]=find(S[x]); }//按秩歸并，將根結(jié)點(diǎn)數(shù)量少的樹連接到根結(jié)點(diǎn)多的樹，這里用S[root]表示根結(jié)點(diǎn)//S[root]為負(fù)數(shù)，絕對(duì)值為節(jié)點(diǎn)數(shù) void Union(int root1,int root2){ if(S[root1]>S[root2]){S[root2]+=S[root1];S[root1]=root2;}else {S[root1]+=S[root2];S[root2]=root1;} }

?

?

程序框架：

?

?

最終代碼如下：

?

#include<cstdio> #define Maxitem 10000int S[Maxitem]; //采用路徑壓縮，尾遞歸尋找他的根結(jié)點(diǎn) int find(int x){if(S[x]<0)return x;////先找到根； 把根變成 X 的父結(jié)點(diǎn)； 再返回根。else return S[x]=find(S[x]); }//按秩歸并，將根結(jié)點(diǎn)數(shù)量少的樹連接到根結(jié)點(diǎn)多的樹，這里用S[root]表示根結(jié)點(diǎn)//S[root]為負(fù)數(shù)，絕對(duì)值為節(jié)點(diǎn)數(shù) void Union(int root1,int root2){ if(S[root1]>S[root2]){S[root2]+=S[root1];S[root1]=root2;}else {S[root1]+=S[root2];S[root2]=root1;} } void initialzation(int n){for(int i=0;i<n;i++){S[i]=-1;} } void Input_connection(){int u,v,root1,root2;scanf("%d %d",&u,&v);getchar();root1=find(u-1);root2=find(v-1);Union(root1,root2); } void Check_connection(){int u,v,root1,root2;scanf("%d %d",&u,&v);getchar();root1=find(u-1);root2=find(v-1);if(root1==root2)printf("yes\n");else printf("no\n"); } void Check_networks(int n){int count=0;for(int i=0;i<n;i++)if(S[i]<0)count++;if(count==1)printf("The network is connected.\n");else printf("There are %d components.\n",count); } int main(){char in;int n;scanf("%d",&n);initialzation(n);do{scanf("%c",&in);switch(in){case'I':Input_connection();break;case'C':Check_connection();break;case'S':Check_networks(n);break;}}while(in!='S');return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/patatoforsyj/p/9828473.html

總結(jié)

以上是生活随笔為你收集整理的File Transfer(并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。