两道有关欧拉回路的例题
POJ1300-Door Man
//判定是否存在从某点到0点的欧拉回路//Time:0Ms Memory:116K#include#include #include using namespace std;#define MAX 25int st, n;int door[MAX];int main(){ char s[120]; while (scanf("%s", s), strcmp(s, "ENDOFINPUT")) { memset(door, 0, sizeof(door)); int doors = 0; scanf("%d%d", &st, &n); gets_s(s, 120); for (int i = 0; i < n; i++) { gets_s(s, 120); int num, k = 0; while (sscanf(s + k, "%d", &num) == 1) { doors++; door[num]++; door[i]++; while (s[k] == ' ') k++; while (s[k] && s[k] != ' ') k++; } } gets_s(s, 120); int odd = 0; for (int i = 0; i < n; i++) odd += door[i] % 2 == 1; if (odd == 0 && st == 0) printf("YES %d\n", doors); //无奇度节点 else if (odd == 2 && st && door[st] % 2 && door[0] % 2) printf("YES %d\n", doors); //两个奇度节点 else printf("NO\n"); } return 0;}
POJ1386-Plays on Words
//判断能否使给定的词组前后接龙//Time:344Ms Memory:120K#include#include #include using namespace std;#define MAX 28#define MAXS 1005#define MAXN 100005int n;char s[MAXS];int in[MAX], out[MAX];int fa[MAX];int find(int x){ return fa[x] < 0 ? x : find(fa[x]);}int Union(int r1, int r2){ r1 = find(r1); r2 = find(r2); if (r1 == r2) return r1; int tmp = fa[r1] + fa[r2]; if (fa[r1] > fa[r2]) { fa[r1] = r2; fa[r2] = tmp; return r2; } else { fa[r2] = r1; fa[r1] = tmp; return r1; }}int main(){ //freopen("words.in", "r", stdin); int T; scanf("%d", &T); while (T--) { memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(fa, -1, sizeof(fa)); int pa; scanf("%d", &n); while (n--) { scanf("%s", s); int i = s[strlen(s) - 1] - 'a'; int o = s[0] - 'a'; out[o]++; in[i]++; pa = Union(i, o); } int odd = 0; bool connect = true; bool A = false, B = false; for (int i = 0; i < 26; i++) { if (!in[i] && !out[i]) continue; if (pa != find(i)) { connect = false; break; } if (in[i] - out[i] != 0) { odd++; if (in[i] - out[i] == 1) A = true; if (in[i] - out[i] == -1) B = true; } } if (connect && ((odd == 2 && A && B) || odd == 0)) printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0;}