题解 | #Is It A Tree?#

#include<iostream>
using namespace std;

const int MAXN = 10001;
int father[MAXN];
bool visited[MAXN];
int Indegree[MAXN];
int index = 0;
void initConfig()
{ 
	for (int i = 0; i < MAXN; i++)
	{
		father[i] = i;
	}
	fill(visited, visited + MAXN, false);
	fill(Indegree, Indegree + MAXN, 0);
	index++;
}

int findFather(int x)
{
	if (x == father[x])
	{
		return x;
	}
	else
	{
		father[x] = findFather(father[x]);
		return father[x];
	}
}
void  UnionFather(int x,int y)
{
	int x_father = findFather(x);
	int y_father = findFather(y);
	father[y_father] = x_father;
}

bool isTree()
{
	int parts = 0;
	for (int i = 0; i < MAXN; i++)
	{
		if (!visited[i]) continue;
		if (i == findFather(i)) 
		{
			parts++;
			if (Indegree[i] != 0)
			{
				return false;
			}
		}
		else  if(Indegree[i]>1)
		{
			return false;
		}		
	}
	if (parts > 1)
	{
		return false;
	}
	return true;
}

int main()
{
	int a, b;
	initConfig();
	while (scanf("%d %d",&a,&b)!=EOF)
	{
		if (a == -1) 
		{
			break;
		}
		else if (a != 0)
		{
			visited[a] = true;
			visited[b] = true;
			UnionFather(a, b);
			Indegree[b]++;

		}
		else
		{
			if (isTree())
			{
				printf("Case %d is a tree.\n",index);
			}
			else
			{
				printf("Case %d is not a tree.\n", index);
			}
			initConfig();
		}
	}
}