本文共 2334 字,大约阅读时间需要 7 分钟。
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?
Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), 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.
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.
5C 3 2I 3 2C 1 5I 4 5I 2 4C 3 5S
nonoyesThere are 2 components.
5C 3 2I 3 2C 1 5I 4 5I 2 4C 3 5I 1 3C 1 5S
nonoyesyesThe network is connected.
代码如下:
/*并查集的查找与合并一开始初始化集合的个数为n个..然后每两个集合合并就将集合数减一..最后判断集合个数是否为一来判定是否两两相互连接...*/#include#include #include #include using namespace std;const int maxn=10005;int n;int a[maxn];int num;char op[5];void init(){ num=n; for (int i=1;i<=n;i++) { a[i]=i; }}int Find(int x){ if(a[x]==x) return x; else return a[x]=Find(a[x]);}void unit(int x,int y){ int px=Find(x); int py=Find(y); if(px!=py) { a[px]=py; num--; }}int main(){ scanf("%d",&n); init(); while (scanf("%s",op)&&op[0]!='S') { int x,y; scanf("%d%d",&x,&y); if(op[0]=='I') { unit(x,y); } else { if(Find(x)==Find(y)) { printf("yes\n"); } else printf("no\n"); } } if(num==1) printf("The network is connected.\n"); else printf("There are %d components.\n",num); return 0;}
转载地址:http://gxaen.baihongyu.com/