TOJ::169 / 高棕櫚的意外收穫

http://2014.sprout.csie.org/oj/pro/169/
這題是尤拉路徑或是迴路。

基本上找尤拉迴路，路徑的方法就是直接DFS，並且在return前print 離開的點，就會是一個尤拉路徑或迴路，唯一要注意的是如果有奇點(只可能有兩個，否則無法構成尤拉迴路)的話，要選一個開始。

但是這題要求字典序最小，所以不能直接做，首先 adjacency lists 應該先排序，我用adjacency matrix 就省去排序的問題了。再來是重邊，我一開始用bool記錄邊，WA了好久。最後是判斷是不是奇點，是把全部的邊加起來%2，我一開是忘記了QAQ。

#include <cstdlib>
#include <iostream>
#include <cstring>
#define N 501
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int D[N][N];
int ST[1026],st=0;
void DFS(int now){
    F(500)if(D[now][i+1]){
        D[now][i+1]--,D[i+1][now]--;
        DFS(i+1);
    }
    ST[st++]=now;
    return;
}
int main(int argc,char *argv[])
{
    ios_base::sync_with_stdio(false);
    int n,a,b;
    cin>>n;
    F(n){
        cin>>a>>b;
        D[a][b]++,D[b][a]++;
    }
    int go=1;
    F(500){
        int sum=0;
        Fi(j,500){
            sum+=D[i+1][j+1];
        }
        if(sum%2){
            //cout<<"TT "<<i+1<<endl;
            go=i+1;
            break;
        }
    }
    DFS(go);
    for(int i=st-1;i>=0;i--)cout<<ST[i]<<endl;
    system("pause");
    return 0;
}