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:
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 | 5 |
Sample Output 1:
1 | no |
Sample Input 2:
1 | 5 |
Sample Output 2:
1 | no |
题意分析
题目大意
建立n个结点,在建立边之后判断两结点是否能连通,且判断是否有多个顶点
这道题主要考察的就是并查集的运用,这里的并查集可以通过数组索引来作为结点位置而数组下标作为结点的父结点.通过并查集性质的Find函数可以找到其结点的父结点,通过判断父结点是否与要判断的结点相同若相同则说明连通,而在其插入边的过程中通过并查集中小树贴到大树上来进行按秩归并,最后通过数组下标为负数的个数来判断有多少个根结点,这道题就解决了
其中Find函数采用了路径压缩的递归方法即将结点的父结点递归为根结点,从而缩小查询的复杂度
答案
1 |
|