浙大数据结构习题笔记：05-树8 File Transfer (25分)

05-树8 File Transfer (25分)

原题

总结

这道题就是并查集的配套习题，之前学校在学图的算法时就提到过要使用并查集实现，但因为没细讲并查集的实现导致我学的一知半解(
学完这个后，觉得还可以，这里面的并查集还是比较好实现的，通过数组下标记录对应值，数组中存储的是每个值的父节点的位置。Find和Union采用极简的操作如下

int Find(SetType S[],int n)
{
	for(;S[n] >= 0;n = S[n]);
	return x;
}

void Union(SetType s[],int x1,int x2){
	S[x2] = S[x1];
}

但是以这样的极简方法来做，可能会造成超时
于是我们采用按秩归并和路径压缩的方法简化时间，具体操作如下程序
其中的按秩归并，我们设根节点的值为-元素个数，就是值为这个根下面所有元素个数的负数，如果根后无节点，就是-1，以这样的方式，我们可以做到在归并的过程中，将元素少的根节点并到元素多的根结点上，使得树的高度不会必然增加

在路径压缩中，我们采用一个尾递归的方式，在递归过程中将一个高度很高的树打散，分别接在第一个节点上，具体作用如图

具体代码实现

#include<cstdio>
#define MaxSize 10005
typedef int SetType; 
using namespace std;

void Init(SetType s[],int n){
	for(int i=0;i<n;i++)
		s[i] = -1;
}

int Find(SetType s[],int x){
	if(s[x] < 0)  // 本身已经是根 
		return x;
	else  // 1. 找到根  2. 把根变成 x 的父结点  3.再返回根 
		return s[x] = Find(s,s[x]);
} 

void Union(SetType s[],int x1,int x2){
    //S[root] = -元素个数
    if(s[x1] < s[x2]){  //x1的元素多，少的并入多的中
		s[x1] += s[x2];
		s[x2] = x1;
	}else{
		s[x2] += s[x1];
		s[x1] = x2;
	}
} 

void Input_connection(SetType s[]){
	int x1,x2;
	scanf("%d %d",&x1,&x2);
	int root1 = Find(s,x1-1);  // 以数组下标存值，下标与存值差 1 
	int root2 = Find(s,x2-1);
	if(root1 != root2)
		Union(s,root1,root2);
}

void check_connection(SetType s[]){
	int x1,x2;
	scanf("%d %d",&x1,&x2);
	int root1 = Find(s,x1-1);
	int root2 = Find(s,x2-1);
	if(root1 == root2)
		printf("yes\n");
	else
		printf("no\n");
} 

void check_network(SetType s[],int n){
	int counter = 0;
	for(int i=0;i<n;i++)
		if(s[i] < 0)
			counter++;
	if(counter == 1)
		printf("The network is connected.");
	else
		printf("There are %d components.",counter);
}


int main(){
	int n;
	char in;
	scanf("%d",&n); 
	SetType s[MaxSize];
	Init(s,n);
	do{
		getchar();
		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');

	return 0;
}