File Transfer
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≤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.
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 |
5 |
Sample Output 1:
1 |
no |
Sample Input 2:
1 |
5 |
Sample Output 2:
1 |
no |
一道典型的并查集的题目,刚开始没想太多,直接上了结构数组,结果当然超时了,简直惨不忍睹。代码如下:
1 |
|
看了老师的提示,由于编号为1—N,可以直接用数组表示并查集,利用按秩归并进行优化,即将小集合并到大集合上,代码如下:
1 |
|
近期评论