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;
}