05-树8 File Transfer (25分)

原题链接

#include <stdio.h>
#define MaxSize 10001
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MaxSize];
//初始化
void Init(SetType s,int n)
{
	int i;
	for(i = 0;i < n;i++)
		s[i] = -1;
}

//查找
int Find(SetType s,int x)
{
	if(s[x] < 0)
		return x;
	else//未找到根节点，将父节点即S[x]当成儿子递归调用，直至找到根节点，即S[x]<0
		return s[x] = Find(s,s[x]);
}

//集合的并运算
void Union(SetType s,int x1,int x2)
{
	if(s[x1] < s[x2])//x2规模大
	{
		s[x1] += s[x2];//两树规模相加
		s[x2] = x1;//将x1挂在x2上
	}
	else
	{
		s[x2] += s[x1];
		s[x1] = x2;
	}
	//printf("%d %d\n",s[x2],s[x1]);
}

//将两台电脑连接
void InputConnection(SetType s)
{
	int x1,x2,root1,root2;
	scanf("%d %d",&x1,&x2);
	root1 = Find(s,x1-1);
	root2 = Find(s,x2-1);
	//printf("%d %d\n",root1,root2);
	if(root1 != root2)
		Union(s,root1,root2);
}

//判断两台电脑是否连接
void CheckConnection(SetType s)
{
	int x1,x2,root1,root2;
	scanf("%d %d",&x1,&x2);
	root1 = Find(s,x1-1);
	root2 = Find(s,x2-1);
	if(root1 == root2)
		printf("yes\n");
	else
		printf("no\n");
}

//网络个数
void Internet(SetType s,int n)
{
	int count,i;
	count = 0;
	for(i = 0; i < n;i++)
		if(s[i] < 0)
			count++;
	if(count == 1)
		printf("The network is connected.\n");
	else
		printf("There are %d components.\n",count);
}

int main()
{
	int n;
	char input;
	scanf("%d\n",&n);
	SetType s;
	Init(s,n);
	do{
		scanf("%c",&input);
		switch(input)
		{
			case 'I':InputConnection(s);break;
			case 'C':CheckConnection(s);break;
			case 'S':Internet(s,n);break;
		}
	}while(input != 'S');
	return 0;
}