UVA 10054 The Necklace ( Euler's Path )

UVa Online Judge
可以把顏色當作節點，則珠子就是節點之間的邊，題目要求就等價於問是否能用每個邊恰好一次構成一個迴路。這就是經典的尤拉迴路問題。
若滿足"所有點構成的圖聯通且不存在奇度數的節點"則必有尤拉迴路( 而且隨便走都是 )，而尤拉路徑除此之外還允許兩個奇點存在( 一頭一尾 )。
這題要特別注意的是存在重邊，所以要用++ / -- 處理邊數，還有輸出時要逆序( 後序 )，因為會有迴朔的問題，可以想像是一個節點多方向延伸，所以不能前序輸出。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 5;

int kase;
int n;
int vis[MAXN], deg[MAXN], G[MAXN][MAXN];

bool hasOdd(){
    for(int i = 1; i <= 50; ++i)
        if( deg[i] & 1 )
            return true;
    return false;
}

void euler(int u){
    for(int v = 1; v <= 50; ++v)
        if( G[u][v] ){ // 隨便走都對，把無向邊刪去再繼續
            --G[u][v], --G[v][u];
            euler( v );
            printf("%d %d\n", v, u);
        }
}

void solve(){
    if( hasOdd() ){
        puts("some beads may be lost");
        return;
    }
    for(int i = 1; i <= 50; ++i)
        if( deg[i] ){
            euler( i );
            break;
        }
}

void init(){
    memset( G, 0, sizeof(G) );
    memset( deg, 0, sizeof(deg) );
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        printf("Case #%d\n", ++kase);
        scanf("%d", &n);
        init();
        for(int i = 0; i < n; ++i){
            int a, b; scanf("%d %d", &a, &b);
            ++G[a][b], ++G[b][a], ++deg[a], ++deg[b];
        }
        solve();
        if( T ) puts("");
    }
    return 0;
}