1426.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1426 on 2005-11-28 at 10:26:53 */ 
#include <cstdio>
#include <cstring>

const int MAX = 32;

int door[MAX][MAX];

bool DFS(const int);

int main()
{
	int i, j, src, n, m, dn;
	int id[MAX], odd;
	char info[MAX], ch;
	bool euler;

	while(scanf("%s", info) != EOF && strcmp(info, "ENDOFINPUT")) {
		scanf("%d %d", &src, &n);
		dn = 0;
		getchar();
		memset(door, 0, sizeof(door));
		for(i = 0; i < n; i++) {
			while(true) {
				if((ch = getchar()) == '\n') {
					break;
				} else if(ch != ' ') {
					ungetc(ch, stdin);
					scanf("%d", &m);
					door[i][m]++;
					door[m][i]++;
					dn++;
				}
			}
		}
		euler = true;
		odd = 0;
		if(!DFS(n)) {
			euler = false;
		} else {
			memset(id, 0, sizeof(id));
			for(i = 0; i < n; i++) {
				for(j = 0; j < n; j++) {
					id[i] += door[i][j];
				}
				if(id[i] % 2 != 0) {
					odd++;
				}
			}
			if(src == 0) {
				if(odd != 0) {
					euler = false;
				}
			} else {
				if(odd != 2 || id[src] % 2 == 0 || id[0] % 2 == 0) {
					euler = false;
				}
			}
		}
		scanf("%s", info);
		if(euler) {
			printf("YES %d\n", dn);
		} else {
			printf("NO\n");
		}
	}
	
	return 0;
}

bool DFS(const int n)
{
	int stack[MAX], top = 0;
	bool visit[MAX] = {false};
	int i, j;
	
	stack[top++] = 0;
	visit[0] = true;
	while(top > 0) {
		int p = stack[--top];
		for(i = 0; i < n; i++) {
			if(door[p][i] != 0 && !visit[i]) {
				stack[top++] = i;
				visit[i] = true;
			}
		}
	}
	for(i = 0; i < n; i++) {
		for(j = 0; j < n && !visit[j]; j++) {
			if(door[i][j] != 0) {
				return false;
			}
		}
	}
	return true;
}