POJ 1300 Door Man：無向圖歐拉路徑判定

題目大意

房子有 N 個房間（0~N-1）和 X 扇門連接房間，圖連通。每經過一扇門即關閉。問從 M 號房出發，能否走遍所有門並到達 0 號房。

解題思路

此為固定起點終點的無向圖歐拉路徑問題。無向圖存在歐拉路徑的充要條件：

1. 圖連通（題目保證）。
2. 奇度頂點數為 0 或 2。

因起點 M、終點 0 固定，故只有兩種合法情況：

• 所有頂點度數均為偶數（歐拉迴路），且 M == 0。
• 僅 M 和 0 為奇度，其餘為偶數（歐拉路徑），且 M != 0。

統計各頂點度數即可判斷。輸出 YES 門數 或 NO。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    char str[1005];
    while (scanf("%s", str), strcmp(str, "ENDOFINPUT")) {
        int m, n; scanf("%d%d", &m, &n); getchar();
        vector<int> deg(n, 0);
        int doors = 0;
        for (int i = 0; i < n; ++i) {
            gets(str);
            for (int j = 0; str[j]; ++j)
                if (isdigit(str[j])) {
                    int v = str[j] - '0';
                    deg[i]++; deg[v]++; doors++;
                }
        }
        scanf("%s", str); // 讀取 END
        int odd = 0;
        for (int d : deg) if (d & 1) odd++;
        bool ok = (odd == 0 && m == 0) || (odd == 2 && (deg[m]&1) && (deg[0]&1) && m != 0);
        if (ok) printf("YES %d\n", doors);
        else puts("NO");
    }
    return 0;
}