Uva 10596 - Morning Walk 歐拉回路基礎水題 並查集實現

題目給出圖，要求判斷不能一遍走完所有邊，也就是無向圖，題目分類是分歐拉回路，但其實只要判斷度數就行了。

一開始以為只要判斷度數就可以了，交了一發WA了。聽別人說要先判斷是否是聯通圖，於是用並查集並一起，然後判斷是否有多個根。

用dfs的話就是深搜時標記下，最後看看有沒有全部標記。我沒用dfs做。

代碼：

#include <cstdio>  
const int maxn = 201; 
int f[maxn]; 
int d[maxn]; 
int find(int x) { 
    if (x != f[x]) 
        return f[x] = find(f[x]); 
    return x; 
} 
int main() { 
    int n, r; 
    while (scanf("%d%d", &n, &r) != EOF) { 
        bool ok = 1; 
        int ans = 0; 
        for (int i = 0; i < n; i++) 
            d[i] = 0, f[i] = i; 
        int a, b; 
        for (int i = 0; i < r; i++) { 
            scanf("%d%d", &a, &b); 
            f[find(a)] = find(b); 
            d[a]++; 
            d[b]++; 
        }//for  
        if (r <= 1 || n == 0) 
            ok = 0; 
        for (int i = 0; ok && i < n; i++) 
            if (f[i] == i && ans++ > 0) 
                ok = 0; 
        for (int i = 0; ok && i < n; i++) 
            if (d[i] % 2 != 0) { 
                ok = 0; 
                break; 
            } 
        if (ok) 
            printf("Possible\n"); 
        else 
            printf("Not Possible\n"); 
    }//while  
    return 0; 
}