欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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?

05-树8 File Transfer (25分)
05-树8 File Transfer (25分)

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元素所组成。
    参考链接
相关标签: 数据结构 算法