题解 | #Is It A Tree?#

//土尔逊Torson 编写于2023/06/20
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN12801 = 10000;

int father12801[MAXN12801];  //父亲结点
int height12801[MAXN12801];  //结点高度
int inDegree12801[MAXN12801];//入度
bool visit12801[MAXN12801];  //标记

void Initial12801() {             //初始化
	for (int i = 0; i < MAXN12801; i++) {
		father12801[i] = i;
		height12801[i] = 0;
		inDegree12801[i] = 0;
		visit12801[i] = false;
	}
}

int Find12801(int x) {       //查找根结点
	if (x != father12801[x]) {
		father12801[x] = Find12801(father12801[x]);
	}
	return father12801[x];
}

void Union12801(int x, int y) {//合并集合
	x = Find12801(x);
	y = Find12801(y);
	if (x != y) {
		if (height12801[x] < height12801[y]) {
			father12801[x] = y;
		}
		else if (height12801[y] < height12801[x]) {
			father12801[y] = x;
		}
		else {
			father12801[y] = x;
			height12801[x]++;
		}
	}
	return;
}

bool IsTree12801() {
	bool flag = true;
	int component = 0;         //连通分量数目
	int root = 0;              //根结点数目
	for (int i = 0; i < MAXN12801; ++i) {
		if (!visit12801[i]) {
			continue;
		}
		if (father12801[i] == i) {
			component++;
		}
		if (inDegree12801[i] == 0) {
			root++;
		}
		else if (inDegree12801[i] > 1) {  //入度不满足要求
			flag = false;
		}
	}
	if (component != 1 || root != 1) { //不符合树定义
		flag = false;
	}
	if (component == 0 && root == 0) {
		flag = true;
	}
	return flag;
}

int main() {
	int x, y;
	int caseNumber = 0;
	Initial12801();
	while (scanf("%d%d", &x, &y) != EOF) {
		if (x == -1 && y == -1) {
			break;
		}
		if (x == 0 && y == 0) {
			if (IsTree12801()) {
				printf("Case %d is a tree.\n", ++caseNumber);
			}
			else {
				printf("Case %d is not a tree.\n", ++caseNumber);
			}
			Initial12801();
		}
		else {
			Union12801(x, y);
			inDegree12801[y]++;
			visit12801[x] = true;
			visit12801[y] = true;
		}
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")