05-树8 File Transfer (25分)
程序员文章站
2022-03-27 14:08:44
...
题目描述
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?
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.
题意
- 我们有几台电脑,当我们想从一台电脑发送文件到另外一台电脑时,得保证是连通的,所以我们要来判断两台电脑之前是否连通,以及当不连通时,将之连通,检查最后分为几个集合(连通的电脑分为一个集合)
- 当为‘I’时,说明要将输入的两台电脑连通
- 当为‘C’时,说明要检查两台电脑是否连通
- 当为‘S’时,说明要停下来,并输出有几个集合
思路
- 这里采用了并查集的概念,所有的电脑一开始都初始化为-1,表明自己是个孤立的节点,是root。
- 当为‘I’时,说明要将输入的两台电脑连通。首先检查这两台电脑是否处于同一个集合(也就是他们的根节点是否相同),因此我们需要先查找这两台电脑的root是否相同。若处于同一个集合,则什么都不做;若处于不同的集合,则将这两个集合合并。
-
合并:有两种方式来进行合并。
(1)按高度合并
(2)按规模(数量)大小合并 :一开始初始化各个电脑的值都为-1,我们合并总是将小规模的集合合并到大规模集合上。如果A的规模大于B的规模,则B指向A(也就是S[B]=A),反之同理。
(3)这两种合并都为按秩合并,一般来说,选用按规模合并,因为按规模合并与路径压缩经常结合在一起。 - 当为‘C’时,说明要检查两台电脑是否连通。检查是否连通,只要看这两台电脑的root是否相同就可以了。
- 当为‘S’时,说明要停下来,并输出有几个集合。看有几个集合,只要扫描一下所有的电脑,看有哪个电脑的root
#include <stdio.h>
#define MAXN 1000
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MAXN];
void Initialization(SetType S,int n);
void Union(SetType S,SetName root1,SetName root2);
SetName Find(SetType S,ElementType X);
void Input_connection(SetType S);
void Check_network(SetType S,ElementType n);
void Check_connection(SetType S);
int main()
{
SetType S;
/* 1. 初始化集合*/
int n;
char in;
scanf("%d",&n);
Initialization(S,n);
do{
scanf("%c",&in);
switch(in){
case 'I': Input_connection(S); break;
case 'C': Check_connection(S); break;
case 'S': Check_network(S,n); break;
}
} while(in!='S');
}
void Initialization(SetType S,int n)
{
for(int i = 0; i < n;i++)
{
S[i] = -1;
}
}
// 集合的合并 按规模合并
void Union(SetType S,SetName root1,SetName root2)
{
if(S[root2] < S[root1])
{
S[root2] += S[root1];
S[root1] = root2;
}
else{
S[root1] += S[root2]; //由于指向root1,因此root1节点数量增加了root2个节点
S[root2] = root1; // 将root2指向root1
}
}
// 路径压缩方法
SetName Find(SetType S,ElementType X)
{
//若小于0,说明X就是根节点,返回根节点的index 也就是X
if(S[X] < 0)
{
return X;
}
else
{
// 若大于等于0,说明不是根节点,要递归的向上找,
// 先找到根;把根变成X的父节点;再返回根
return S[X] = Find(S,S[X]);
}
}
void Input_connection(SetType S)
{
ElementType u,v;
SetName root1,root2;
scanf("%d %d\n",&u,&v);
// 在插入前 我们需要检查是否在同一个集合 若在同一个集合则不必进行合并
// 如何判断是否在同一个集合 就是找到他们的根,看根是否相同
// 由于index从0开始,因此u应该减1
root1 = Find(S,u-1);
root2 = Find(S,v-1);
if(root1!=root2)
{
Union(S,root1,root2);
}
}
void Check_network(SetType S,ElementType n)
{
int i,counter = 0;
for(i = 0; i < n;i++)
{
if(S[i] < 0)
{
counter++;
}
}
if(counter == 1)
{
printf("The network is connected.\n");
}
else
{
printf("There are %d components.",counter);
}
}
void Check_connection(SetType S)
{
ElementType u,v;
SetName root1,root2;
scanf("%d%d",&u,&v);
root1 = Find(S,u-1);
root2 = Find(S,v-1);
if(root1!=root2)
{
printf("no\n");
}
else{
printf("yes\n");
}
}
注意点
typedef ElementType SetType[MAXN];
- 上面代码定义了一个元素类型为ElementType,含有MAXN个元素的数组类型SetType
- 若不使用typedef保留字,则就变成了数组定义,表示定义了一个元素类型为ElementType、含有10个元素的数组SetType。
- 这两种定义有着本质的区别,若定义的是数组SetType,系统将为它分配有保存MAXN个存储单元;若定义的是数组类型SetType,系统只是把该类型的有关信息登记下来,待以后利用该类型定义对象时使用,具体地说,就是把SetType的元素类型SetType,类型长度,类型名等登记下来,待以后定义SetType类型的对象时使用。
SetType S,S1;
- 上面代码定义了SetType类型的对象S和对象S1,每个对象都是SetType类型的一个数组,每个数组由MAXN个int元素所组成。
参考链接