1098.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1098 on 2005-11-10 at 20:59:17 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;

class UFSet {
private:
	int parent[MAX];
public:
	void makeSet() {
		memset(parent, -1, sizeof(parent));
	}
	int find(int x) {
		if(parent[x] == -1) {
			return x;
		} else {
			parent[x] = find(parent[x]);
			return parent[x];
		}
	}
	void unionSet(int x, int y) {
		int px = find(x);
		int py = find(y);
		if(px != py) {
			parent[px] = py;
		}
	}
};

int main()
{
	UFSet ufs;
	int x, y, f, p;
	int i, j, k, n, m;
	bool edge[MAX][MAX];
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			memset(edge, false, sizeof(edge));
			while(scanf("%d", &x) == 1) {
				if(x == 0) {
					break;
				} else {
					while(true) {
						if(getchar() == '\n') {
							break;
						} else {
							scanf("%d", &y);
							edge[x][y] = edge[y][x] = true;
						}
					}
				}
			}
			m = 0;
			for(i = 1; i <= n; i++) {
				ufs.makeSet();
				f = -1;
				for(j = 1; j <= n; j++) {
					if(j != i) {
						for(k = 1; k <= n; k++) {
							if(k != i && edge[j][k]) {
								ufs.unionSet(j, k);
							}
						}
					}
				}
				for(j = 1; j <= n; j++) {
					if(j != i) {
						p = ufs.find(j);
						if(f == -1) {
							f = p;
						} else if(p != f) {
							m++;
							break;
						}
					}
				}
			}
			printf("%d\n", m);
		}
	}

	return 0;
}