浙江大学数据结构MOOC-课后习题-第五讲-树8 File Transfer

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

我们有一个计算机网络和一系列双向连接。这些连接允许从一个计算机向另一个计算机传输文件。是否可能从网络中的任何计算机向任何其他计算机发送文件？

输入规范：
每个输入文件包含一个测试案例。对于每个测试案例，第一行包含N（2≤N≤10^4），网络中计算机的总数。网络中的每台计算机由1和N之间的正整数表示。然后，在接下来的行中，输入以以下格式给出：
I c1 c2
其中I代表输入c1和c2之间的连接；或
C c1 c2
其中C代表检查是否可能在c1和c2之间传输文件；或
S
其中S代表停止此案例。

输出规范：
对于每个C案例，在一行中打印单词"yes"或"no"，分别表示是否可能在c1 和c2之间传输文件。在每个案例的末尾，在一行中打印"The network is connected.“，如果任何一对计算机之间存在路径；或"There are k components.”，其中k是这个网络中的连通分量的数量。
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

思路分析

①本题怎么存储并查集
由于题目中所给计算机编号是从1到N，因此可以映射到数组下标0到N-1；则可将数组下标作为计算机编号，数组值作为计算机所在集合的根节点

当计算机本身为根节点时，那么数组值就代表集合中元素的规模大小的负数（这里为负数的原因是为了标识它的根节点的身份）

②怎么查找根节点
由于非根节点的数组值均为正，利用此特征则可以循环遍历找到根节点
③怎么合并集合
由于常规的不加限制的合并会导致出现时间复杂度为O(n²）的情况（详解请看视频：小白-FT.3 按秩归并）
因此有两种优化方法：

• 第一种是每次合并时，将树高较小的树合并到树高较大的那棵树上
• 第二种是每次合并时，将集合元素规模较小的树合并到规模更大的树上（本解法采用了第二种）

④需要的注意的点

• 由于计算机编号比数组下标大1，因此在传参时记得要减1
• 数组值为负时，代表自身就是根节点，数组值的绝对值代表了所处集合的元素大小
• 要是测试点全都不通过，尝试检查一下打印的值是否和题目要求中一致（笔者当时做的时候就是单词没打全、或者末尾的句号漏掉了 T_T）

#include <iostream>

#define MAXSIZE 10000

/* 
	数组下标对应(计算机编号-1)
	当数组所存值为正，对应父节点的下标
	当数组所存值为负，代表此节点为根节点，以及此集合中的树高
*/
int a[MAXSIZE];

void init(int N)
{
	for (int i = 0; i < N; i++)
		a[i] = -1;
}
//根据规模来进行合并 此处a[root]值为负
void Union(int root1, int root2)
{	
	//规模大的负过来更小
	if (a[root1] < a[root2])
	{
		a[root1] += a[root2];
		a[root2] = root1;
	}
	else
	{
		a[root2] += a[root1];
		a[root1] = root2;
	}
		
}

//返回根节点索引
//注意:独立节点的根节点就是自身
int findRoot(int X)
{	
	for (; a[X] > 0; X = a[X]);
	return X;
}

void connect()
{	
	int u, v;
	std::cin >> u >> v;
	int root1 = findRoot(u - 1);
	int root2 = findRoot(v - 1);
	if (root1 != root2)
		Union(root1, root2);
}

void check()
{
	int u, v;
	std::cin >> u >> v;
	int root1 = findRoot(u - 1);
	int root2 = findRoot(v - 1);
	if (root1 == root2) std::cout << "yes" << std::endl;
	else std::cout << "no" << std::endl;
}

void stop(int N)
{
	int counter = 0;
	for (int i = 0; i < N; i++)
		if (a[i] < 0) counter++;
	if (counter == 1) std::cout << "The network is connected.";
	else std::cout << "There are " << counter << " components.";
}

int main()
{
	int N;
	char s;
	std::cin >> N;
	init(N);
	do
	{
		std::cin >> s;
		if (s == 'I')
			connect();
		else if (s == 'C')
			check();
		else if (s == 'S')
			stop(N);
	} while (s != 'S');
}
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