题解 | #Is It A Tree?#

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define N 10000  //元素的上限个数
int father[N]; //存储了每个元素父亲的下标
bool visited[N] = { false };

int input[N] = { 0 }; //用于记录结点的入度

void Init() {
	for (int i = 0; i < N; i++) {
		father[i] = i;
		input[i] = 0;
		visited[i] = false;
	}
}

int Findfather(int x) {
	if (x != father[x]) {
		father[x] = Findfather(father[x]);
	}
	return father[x];
}

void Union(int x, int y) {
	x = Findfather(x);
	y = Findfather(y);
	if (x != y) {
		father[y] = x;
	
	}
	
}

bool IsTree() {
	int num = 0, root = 0; //连通分量的数目，根节点的数目
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) continue;
		else {
			if (input[i] > 1) return false;

			if (father[i] == i) {
				num++;
			}
			if (input[i] == 0)
				root++;
		}

	}
    if(root ==0 &&num==0) return true;
    else if (root != 1 || num != 1)
		return false;

	return true;

}


int main() 
{
		Init();  //并查集初始化
		int n, m;
		int index = 1;
		while (cin >> n >> m) {
			if (n == -1 && m == -1) {
				break;
			}
			if (n == 0 && m == 0) {
				if (IsTree())
					cout << "Case " << index++ << " is a tree." << endl;
				else cout << "Case " << index++ << " is not a tree." << endl;
				Init();
				continue;
			}
			if (!visited[n]) visited[n] = true;
			if (!visited[m]) visited[m] = true;    //给每个访问到的结点做标记
			Union(n, m);
			input[m]++;
		}
}