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 containsN(2), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 andN. Then in the following lines, the input is given in the format:

I c1 c2  

whereIstands for inputting a connection betweenc1andc2; or

C c1 c2    

whereCstands for checking if it is possible to transfer files betweenc1andc2; or

S

whereSstands for stopping this case.

Output Specification:

For eachCcase, print in one line the word "yes" or "no" if it is possible or impossible to transfer files betweenc1andc2, 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 arekcomponents." wherekis 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.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int fa[10005];
 5 
 6 int Find(int x){
 7     return  fa[x]==x?x:fa[x]=Find(fa[x]);
 8 }
 9 
10 void Union(int x,int y){
11     x=Find(x);y=Find(y);
12     if(x!=y) fa[x]=y;
13 }
14 
15 int main()
16 {
17     int n;
18     cin>>n;
19     for(int i=0;i<=10005;i++)
20     fa[i]=i;
21     char ch[10];
22     int x,y,a,b;
23     while(scanf("%s",ch)&&ch[0]!='S')
24     {
25         cin>>x>>y;
26         if(ch[0]=='C')
27         printf("%s\n",Find(x)==Find(y)?"yes":"no");
28         else
29         Union(x,y);
30     }
31     int num=0;
32     for(int i=1;i<=n;i++)
33     {
34         num+=(Find(i)==i);
35     }
36     if(num==1)printf("The network is connected.\n");
37     else printf("There are %d components.\n",num);
38     return 0;
39 }

链接：https://blog.csdn.net/Dylan_Frank/article/details/79821374

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

微信扫一扫
关注该公众号