(UVA) 10054 - The Necklace [尤拉路徑、歐拉路徑、Euler Path]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=995

主要來講，就是如果一個圖有Euler Path，那，其中最多只會有兩個點的degree是奇數，而且這些點要互相連通(可以用Disjoint Set(並查集)檢察，我這份code裡面沒有！)

然後呢，要把路徑輸出出來的話，那就按照我的code中的dfs方法即可XD

複雜度(用adj陣列)：O(V^2 + E)
複雜度(用vector)   ：O(V + E)

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX_N = 56;

int adj[MAX_N][MAX_N];
int deg[MAX_N];

void dfs(int i) {
    for (int j=1;MAX_N>j;j++) {
        if (adj[i][j]) {
            adj[i][j]--;
            adj[j][i]--;
            dfs(j);
            printf("%d %d\n",j,i);
        }
    }
}

int main () {
//    freopen("output.txt","w",stdout);
    int T;
    scanf("%d",&T);
    for (int qq=1;T>=qq;qq++) {
        if (qq!=1) puts("");
        memset(adj,0,sizeof(adj));
        memset(deg,0,sizeof(deg));
        int m;
        scanf("%d",&m);
        while (m--) {
            int i,j;
            scanf("%d %d",&i,&j);
            adj[i][j] ++ ;
            adj[j][i] ++ ;
            deg[i]++;
            deg[j]++;
        }
        bool check=false;
        int n=50;
        for (int x=1;n>=x;x++) {
            if (deg[x] & 1) check=true;
        }
        if (check) {
            printf("Case #%d\nsome beads may be lost\n",qq);
        }
        else {
            printf("Case #%d\n",qq);
            for (int i=1;n>=i;i++) {
                if (deg[i]) {
                    dfs(i);
                    break;
                }
            }
        }
    }
}