2120.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2120 on 2005-10-15 at 20:15:27 */ 
#include <cstdio>
#include <cstring>
#define  MAX  512

class UFSet {
public:
	int father[MAX];
	void makeSet() {
		memset(father, -1, sizeof(father));
	}
	int findFather(int x) {
		if(father[x] == -1) {
			return x;
		} else {
			father[x] = findFather(father[x]);
			return father[x];
		}
	}
	void unionSet(int x, int y) {
		int fatherX = findFather(x);
		int fatherY = findFather(y);
		if(fatherX != fatherY) {
			father[fatherX] = fatherY;
		}
	}
};

int main()
{
	UFSet *uf = new UFSet;
	int edgeN, pa, pb, pointN;
	int i, j, f, k, indeg[MAX], inN;;
	bool app[MAX], tree;

	for(i = 1; ; i++) {
		uf->makeSet();
		pointN = 0;
		memset(app, false, sizeof(app));
		memset(indeg, 0, sizeof(indeg));
		for(edgeN = 0; ; edgeN++) {
			scanf("%d %d", &pa, &pb);
			if(pa < 0 && pb < 0) {
				return 0;
			} else if(pa == 0 && pb == 0) {
				break;
			} else {
				if(!app[pa]) {
					app[pa] = true;
					pointN++;
				}
				if(!app[pb]) {
					app[pb] = true;
					pointN++;
				}
				indeg[pb]++;
			}
			uf->unionSet(pa, pb);
		}
		printf("Case %d ", i);
		if(edgeN == 0 && pointN == 0) {
			printf("is a tree.\n");
		} else if(pointN != edgeN + 1) {
			printf("is not a tree.\n");
		} else {
			f = -1;
			k = 0;
			inN = 0;
			tree = true;
			for(j = 1; j < MAX && k != pointN; j++) {
				if(app[j]) {
					if(indeg[j] == 0) {
						inN++;
					}
					if(inN > 1) {
						tree = false;
						break;
					}
					if(f == -1) {
						f = uf->findFather(j);
					} else if(f != uf->findFather(j)) {
						tree = false;
						break;
					}
					k++;
				}
			}
			if(tree) {
				printf("is a tree.\n");
			} else {
				printf("is not a tree.\n");
			}
		}
	}
	
	return 0;
}