05-树8 File Transfer

05-树8 File Transfer

分数 25
作者 陈越
单位 浙江大学

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  
1

where I stands for inputting a connection between c1 and c2; or

C c1 c2    
1

where C stands for checking if it is possible to transfer files between c1 and c2; or

S
1

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:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
1
2
3
4
5
6
7
8

Sample Output 1:

no
no
yes
There are 2 components.
1
2
3
4

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
1
2
3
4
5
6
7
8
9
10

Sample Output 2:

no
no
yes
yes
The network is connected.
1
2
3
4
5

代码长度限制
16 KB
Go (go)
时间限制
400 ms
内存限制
64 MB
Java (javac)
时间限制
400 ms
内存限制
64 MB
Python (python3)
时间限制
400 ms
内存限制
64 MB
其他编译器
时间限制
150 ms
内存限制
64 MB
C++ (g++)

思路：

本题采用并查集，根结点相同则连通，否则不连通。

AC代码：

#include
using namespace std;
#define MAX 10002

int father[MAX]; //存放父节点 
bool isRoot[MAX];//判断是否是根结点

//查找x所在集合的根节点 
int findFather(int x){
	if(x==father[x]) return x;
    else return father[x]=findFather(father[x]);//直接将根结点赋值为当前结点的父亲节点
} 

//合并集合
void Union(int a,int b){
	int faA=findFather(a);
    int fbB=findFather(b);
    if(faA!=fbB)
        father[faA]=fbB;
}	

int main(){
	int N;
	cin>>N;
	char ch;
	int n1,n2;
	cin>>ch;
    //初始化
	for(int i=1;i<=N;i++){
        //设置每个元素父节点为自己 
		father[i]=i;
		isRoot[i]=false;
	}
	while(ch!='S'){
		cin>>n1>>n2;
		if(ch=='C'){
			if(findFather(n1)==findFather(n2)){
				cout<<"yes"<<endl;
			}
			else{
				cout<<"no"<<endl;
			}
		}
		if(ch=='I'){
			Union(n1,n2);
		}
		cin>>ch;
	}
	for(int i=1;i<=N;i++){
		isRoot[findFather(i)]=true;//集合的父节点为根
	}
	int ans=0;//记录集合的数目
	for(int i=1;i<=N;i++){
		ans+=isRoot[i];
	} 
	if(ans==1){
		cout<<"The network is connected.";
	}
	else{
		cout<<"There are "<<ans<<" components.";
	}
	return 0;
} 

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