#include<iostream>

using namespace std;

#define MAX 30000

int father[MAX];

void make_set(int x)
{
	father[x] = x;
}

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

void union_set(int x, int y)      //第二个指向第一个
{
	int f1, f2;
	f1 = find_set(x), f2 = find_set(y);
	father[f2] = f1;
}

int main()
{
	int a[MAX], b[MAX];
	int ncase = 1;
	int i, temp1, temp2;
	bool visit[MAX];
	while(scanf("%d%d", &a[0], &b[0]) && a[0] != -1) {
		int m = 1;
		memset(visit, 0, sizeof(visit));
		if(a[0] == b[0] && a[0] == 0) {
			printf("Case %d is not a tree.\n", ncase ++);
			continue;
		}
		while(scanf("%d%d", &a[m], &b[m ++]) && (a[m - 1] + b[m - 1]))
			;
		for(i = 0; i < m - 1; i ++) {
			make_set(a[i]);
			make_set(b[i]);
		}
		int flag = 0;
		for(i = 0; i < m - 1; i ++) {
			//cout << find_set(a[i]) <<" " << find_set(b[i]) << endl;
			if(visit[b[i]] == 1) {
				flag = 1;
				break;
			}
			visit[b[i]] = 1;
			//cout << find_set(a[i]) <<" " << find_set(b[i]) << endl;
			if(find_set(a[i]) == find_set(b[i])) {
				flag = 1;
				break;
			}
			union_set(a[i], b[i]);	
		}
		if(flag == 1) {
			printf("Case %d is not a tree.\n", ncase ++);
			continue;
		}
		temp1 = find_set(a[0]);
		temp2 = find_set(b[0]);
		for(i = 0; i < m - 2; i ++) {     //不包括 0 0
			for(int j = i + 1; j < m - 1; j ++) {
				if(find_set(b[i]) != find_set(b[j]) || find_set(a[i]) != find_set(a[j])) {
					flag = 1;
					break;
				}
			}
			if(flag == 1)
				break;
		}
	//	for(i = 0; i < m - 1; i ++)
	//		cout << find_set(b[i]) << " ";
		if(flag == 0)
			printf("Case %d is a tree.\n", ncase ++);
		else
			printf("Case %d is not a tree.\n", ncase ++);
	}
	
	return 0;
}

• 解决了 回来发现好水 (0) allen4053040allen 2010-04-16 19:05:56