[C++知识库]PAT File Transfer （C++实现）

题目链接 7-8 File Transfer (25 分)

运行结果

我的代码

#include<iostream>

using namespace std;

typedef int SetName;
typedef int Element;
typedef int* SetType;
typedef int ElementType;

//Find的路径压缩算法
SetName Find(SetType S, ElementType X)
{
	if (S[X] < 0)
		return X;
	else
		return S[X] = Find(S, S[X]);
}

//集合的归并
void Union(SetType S, SetName Root1, SetName Root2)
{
	if (Root1 == Root2 || S[Root1] >= 0 || S[Root2] >= 0)//保证是不同的集合进行归并
		return;
	if (S[Root1] < S[Root2]) {
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
	else {
		S[Root1] += S[Root2];
		S[Root2] = Root1;
	}
}

//是否是同一集合
void IsSameSet(SetType S)
{
	Element C1, C2;
	cin >> C1 >> C2;
	--C1; --C2;
	if (Find(S, C1) == Find(S, C2))
		cout << "yes" << endl;
	else
		cout << "no" << endl;
}

//有几个集合
void NumOfSet(SetType S, int N)
{
	int cnt{ 0 };
	for (int i = 0; i < N; ++i) {
		if (S[i] < 0)
			++cnt;
	}
	if (cnt == 1)
		cout << "The network is connected.";
	else
		cout << "There are " << cnt << " components.";
}

//连接
void Connect(SetType S)
{
	Element E1, E2;
	cin >> E1 >> E2;
	--E1; --E2;
	Union(S, Find(S, E1), Find(S, E2));
}

int main()
{
	int N;//电脑的台数
	cin >> N;

	//数组的初始化过程，每个元素为一个根节点，数的规模为1，用-1表示
	int* arr;
	arr = new int[N];
	for (int i = 0; i < N; ++i) {
		arr[i] = -1;
	}

	char a;//判断将要执行的操作
	bool flag{ true };//是否结束输入字母的标志位
	while (cin >> a && flag ==true) {
		switch (a) {
		case 'C'://核对两台电脑是否属于一个集合
			IsSameSet(arr);
			break;
		case 'I'://将两台电脑连入一个集合
			Connect(arr);
			break;
		case 'S'://判定有几个集合，并结束输入
			NumOfSet(arr, N);
			flag = false;
			break;
		default:
			break;
		}
	}

	delete[] arr;//归还内存
	return 0;
}