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??(), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and?. Then in the following lines, the input is given in the format:
1 |
I c1 c2 |
where?I
?stands for inputting a connection between?c1
?and?c2
; or
1 |
C c1 c2 |
where?C
?stands for checking if it is possible to transfer files between?c1
?and?c2
; or
1 |
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?k
?components.” where?k
?is the number of connected components in this network.
Sample Input 1:
1 2 3 4 5 6 7 8 |
5 C 3 2 I 3 2 C 1 5 I 4 5 I 2 4 C 3 5 S |
Sample Output 1:
1 2 3 4 |
no no yes There are 2 components. |
Sample Input 2:
1 2 3 4 5 6 7 8 9 10 |
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:
1 2 3 4 5 |
no no yes yes The network is connected. |
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
// 梁笔记 // https://zouzhongliang.com #include<stdio.h> #include<stdlib.h> int S[10000]; int N; int Find(int S[],int i) { if(S[i] < 0) { return i; } else return S[i] = Find(S,S[i]); } void Check_connection(int S[]) { int root1,root2; int u, v; scanf("%d %d",&u,&v); root1 = Find(S,u-1); root2 = Find(S,v-1); if(root1 == root2) { printf("yes\n"); } else printf("no\n"); } void Union(int S[],int root1,int root2) { if(S[root2] < S[root1]) { S[root2] += S[root1]; S[root1] = root2; } else { S[root1] += S[root2]; S[root2] = root1; } } void Input_connection(int S[]) { int root1,root2; int u, v; scanf("%d %d",&u,&v); root1 = Find(S,u-1); root2 = Find(S,v-1); if(root1 != root2) { Union(S,root1,root2); } } void Initialization(int S[],int n) { for(int i=0;i<n;i++){ S[i] = -1; } } void Check_network(int S[],int n) { int i, counter=0; for(i=0;i<n;i++){ if(S[i]<0) counter++; } if(counter == 1) printf("The network is connected.\n"); else printf("There are %d components.\n", counter); } int main(void) { char in; scanf("%d",&N); Initialization(S,N); do { scanf("%s",&in); switch(in){ case 'C': Check_connection(S);break; case 'I': Input_connection(S);break; case 'S': Check_network(S,N);break; } } while(in != 'S'); return 0; } |