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 ≤ 1 0 4 10 ^ 4 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
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
Sample Output 1
no
no
yes
There are 2 components.
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
Sample Output 2
no
no
yes
yes
The network is connected.
思路分析
这题的大意是：对于 N 台电脑，每两台电脑之间需要连通才能传输文件，我们主要做两个操作，一个是检查两台电脑之间是否已经连通（C）；另一个是将两台电脑连通（I），最后是检查这 N 台电脑可以分为几个集合（相互连通的电脑就组合成了一个集合，单台电脑也可以看作一个集合）并结束程序。主要考察对并查集的应用，通过对小白专场的学习，可以得到解题思路如下：
集合的简化表示
注意到题目中直接使用电脑的编号（ 1 ~ N ）来代表电脑，可以将其映射到一个长度为 N 的数组中，这 N 台电脑就被顺序存储（ 0 ~ N - 1 ）好了，此时我们就不必需要单独的数据域来存储电脑的编号，只需要一个 parent 索引用于表示电脑之间连通的关系，所有的 parent 一开始都初始化为 -1，表示这 N 台电脑为孤立的状态。代码如下：
typedef struct Set {
int parent;
} Set;
Set *SetInit( int size ) {
Set *set = ( Set *) malloc( sizeof(Set) * size );
for (int i = 0; i < size; i ++) {
set[i].parent = -1;
}
return set;
}
程序框架搭建
这里可以使用 switch-case 搭配 do-while 循环，程序结束的条件设置比较简单，也比较简洁。代码如下：
int main(void)
{
int N, pos1, pos2;
scanf("%d", &N);
Set *set = SetInit(N);
char in;
do {
scanf("%c", &in);
switch (in) {
case 'C':
scanf("%d %d",&pos1, &pos2);
Check_Connection(set, pos1, pos2);
break;
case 'I':
scanf("%d %d",&pos1, &pos2);
Input_Connection(set, pos1, pos2);
break;
case 'S':
Check_Network(set, N);
break;
}
} while ( in != 'S' );
free(set);
return 0;
}
检查连通情况
Check_Connection 函数的实现，其实就是检查两台电脑是否属于同一个集合，在并查集中其实就是检查两台电脑是否是同一个根结点（ FindRoot 函数 ）下，代码如下：
void Check_Connection( Set *set, int pos1, int pos2 ) {
int root1 = FindRoot(set, pos1 - 1);
int root2 = FindRoot(set, pos2 - 1);
if ( root1 == root2 ) {
printf("yes\n");
}
else {
printf("no\n");
}
}
连通操作
Input_Connection 函数，首先需要检查两台电脑是否已经连通，若已经连通的话就不用再连了，否则就要进行连接（ UnionSet 函数 。
void Input_Connection( Set *set, int pos1, int pos2 ) {
int root1 = FindRoot(set, pos1 - 1);
int root2 = FindRoot(set, pos2 - 1);
if ( root1 == root2 ) {
return;
}
UnionSet(set, root1, root2);
}
检查连通集
Check_Network 函数，就是检查根结点（-1）的个数。
void Check_Network( Set *set, int size ) {
int cnt = 0;
for ( int i = 0; i < size; i ++ ) {
if ( set[i].parent < 0 ) {
cnt ++;
}
}
if ( cnt == 1 ) {
printf("The network is connected.\n");
}
else {
printf("There are %d components.\n", cnt);
}
}
FindRoot 与 UnionSet 的实现
最关键的部分，是并查集的核心操作，也是后续优化的主要部分。
- FindRoot 函数：
经过之前的描述，这里应该很好理解。
int FindRoot( Set *set, int idx ) {
while ( set[idx].parent >= 0 ) {
idx = set[idx].parent;
}
return idx;
}
- UnionSet 函数
最初版本，不考虑效率，直接将第一个集合的根结点赋为第二个集合的根结点。
void UnionSet( Set *set, int idx1, int idx2 ) {
set[idx1].parent = idx2;
}
初级代码
综上，得到如下代码：
#include <stdio.h>
#include <stdlib.h>
typedef struct Set {
int parent;
} Set;
Set *SetInit( int size ) {
Set *set = ( Set *) malloc( sizeof(Set) * size );
for (int i = 0; i < size; i ++) {
set[i].parent = -1;
}
return set;
}
int FindRoot( Set *set, int idx ) {
while ( set[idx].parent >= 0 ) {
idx = set[idx].parent;
}
return idx;
}
void UnionSet( Set *set, int idx1, int idx2 ) {
set[idx1].parent = idx2;
}
void Input_Connection( Set *set, int pos1, int pos2 ) {
int root1 = FindRoot(set, pos1 - 1);
int root2 = FindRoot(set, pos2 - 1);
if ( root1 == root2 ) {
return;
}
UnionSet(set, root1, root2);
}
void Check_Connection( Set *set, int pos1, int pos2 ) {
int root1 = FindRoot(set, pos1 - 1);
int root2 = FindRoot(set, pos2 - 1);
if ( root1 == root2 ) {
printf("yes\n");
}
else {
printf("no\n");
}
}
void Check_Network( Set *set, int size ) {
int cnt = 0;
for ( int i = 0; i < size; i ++ ) {
if ( set[i].parent < 0 ) {
cnt ++;
}
}
if ( cnt == 1 ) {
printf("The network is connected.\n");
}
else {
printf("There are %d components.\n", cnt);
}
}
int main(void)
{
int N, pos1, pos2;
scanf("%d", &N);
Set *set = SetInit(N);
char in;
do {
scanf("%c", &in);
switch (in) {
case 'C':
scanf("%d %d",&pos1, &pos2);
Check_Connection(set, pos1, pos2);
break;
case 'I':
scanf("%d %d",&pos1, &pos2);
Input_Connection(set, pos1, pos2);
break;
case 'S':
Check_Network(set, N);
break;
}
} while ( in != 'S' );
free(set);
return 0;
}
运行结果如下：
超时了！！！
代码优化
上面的代码超时了，很容易想到是由于 FindRoot 与 UnionSet 函数所引起的，考虑到随着数据量的不断增大，构造的并查集的树会越来越高，每次查找的时间就会不断变长，效率就降低了，题目中 N 可达 1 0 4 10 ^ 4 104 时，故会超时。
以下提供了两种优化的思路，按秩归并与压缩路径，两者可以混合使用。
1. 按秩归并
对于每个集合的根结点，它们的值为 -1，起始只起到了标记的作用，并没有其他的意义，我们可以将其设为有意义的值，比如树的高度或者树结点的个数，对于本题可以使用树的高度或者树结点的个数的相反数，分别对应按秩归并的两种方案：
- 按树高进行归并
- 按规模进行归并
改进一（高度）：
将较矮的树并到较高的树上，这样树高就不会增加了，只有两棵树一样高才会增加树高，效率也大大提高了。
- 如下图：
小树贴到大树上，树高不变
两棵树等高，树高加一
代码如下：
void UnionSet( Set *set, int idx1, int idx2 ) {
if ( set[idx1].parent > set[idx2].parent ) {
set[idx1].parent = idx2;
}
else {
if ( set[idx1].parent == set[idx2].parent ) {
// 更新树高
set[idx1].parent --;
}
set[idx2].parent = idx1;
}
}
运行结果如下：
改进二（规模）：
除了按树高进行归并，还可以对规模进行归并，更加容易理解。
void UnionSet( Set *set, int idx1, int idx2 ) {
if ( set[idx1].parent > set[idx2].parent ) {
set[idx2].parent += set[idx1].parent;
set[idx1].parent = idx2;
}
else {
set[idx1].parent += set[idx2].parent;
set[idx2].parent = idx1;
}
}
运行结果如下：
2. 压缩路径
除了按秩归并，还可以进行压缩路径，与上相比，效率更高，同时也更难理解。代码如下：
int FindRoot( Set *set, int idx ) {
if ( set[idx].parent < 0 ) {
return idx;
}
return set[idx].parent = FindRoot(set, set[idx].parent);
}
最后一步最为巧妙，同时做了三件事：
- 查找当前结点的根结点索引
- 将当前结点的根结点索引变成当前结点的父结点索引
- 返回当前结点的父结点索引
- 如下图：
压缩路径前：
压缩路径后：
运行结果如下：
最终代码
#include <stdio.h>
#include <stdlib.h>
typedef struct Set {
int parent;
} Set;
Set *SetInit( int size ) {
Set *set = ( Set *) malloc( sizeof(Set) * size );
for (int i = 0; i < size; i ++) {
set[i].parent = -1;
}
return set;
}
int FindRoot( Set *set, int idx ) {
if ( set[idx].parent < 0 ) {
return idx;
}
return set[idx].parent = FindRoot(set, set[idx].parent);
}
void UnionSet( Set *set, int idx1, int idx2 ) {
if ( set[idx1].parent > set[idx2].parent ) {
set[idx2].parent += set[idx1].parent;
set[idx1].parent = idx2;
}
else {
set[idx1].parent += set[idx2].parent;
set[idx2].parent = idx1;
}
}
void Input_Connection( Set *set, int pos1, int pos2 ) {
int root1 = FindRoot(set, pos1 - 1);
int root2 = FindRoot(set, pos2 - 1);
if ( root1 == root2 ) {
return;
}
UnionSet(set, root1, root2);
}
void Check_Connection( Set *set, int pos1, int pos2 ) {
int root1 = FindRoot(set, pos1 - 1);
int root2 = FindRoot(set, pos2 - 1);
if ( root1 == root2 ) {
printf("yes\n");
}
else {
printf("no\n");
}
}
void Check_Network( Set *set, int size ) {
int cnt = 0;
for ( int i = 0; i < size; i ++ ) {
if ( set[i].parent < 0 ) {
cnt ++;
}
}
if ( cnt == 1 ) {
printf("The network is connected.\n");
}
else {
printf("There are %d components.\n", cnt);
}
}
int main(void)
{
int N, pos1, pos2;
scanf("%d", &N);
Set *set = SetInit(N);
char in;
do {
scanf("%c", &in);
switch (in) {
case 'C':
scanf("%d %d",&pos1, &pos2);
Check_Connection(set, pos1, pos2);
break;
case 'I':
scanf("%d %d",&pos1, &pos2);
Input_Connection(set, pos1, pos2);
break;
case 'S':
Check_Network(set, N);
break;
}
} while ( in != 'S' );
free(set);
return 0;
}