[TIOJ 1084] 一筆畫問題

作法：

首先可以知道，如果圖裡沒有奇點，那麼起點選編號最小的點最好，而如果有奇點就選奇點裡編號比較小的那個當起點。既然要字典序最小，那可以想到是某種貪心。從傳統的尤拉路徑的算法來看的話，一種可能是從終點開始DFS，每次都選(和這個點有連還沒走過的邊的)編號最大的點走，這樣等於是讓編號大的點比較晚走，得到的尤拉路徑就是答案。另一種可能是從起點開始DFS，每次都選編號最小的點走，最後得到的尤拉路徑反過來就是答案，因為每次取到的都是最好的。這兩種作法有一個是錯的，至於是哪個根為什麼就留給大家思考(?)
( code 裡當然是對的作法 XD )

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10 ;
struct P{int x,y;};
vector<P> edge ;
vector<int> v[maxn] ;
 
bool cmp(int a,int b)
{
    if(edge[a].x==edge[b].x) return edge[a].y<edge[b].y ;
    if(edge[a].x==edge[b].y) return edge[a].y<edge[b].x ;
    if(edge[a].y==edge[b].x) return edge[a].x<edge[b].y ;
    if(edge[a].y==edge[b].y) return edge[a].x<edge[b].x ;
}
 
bool vis[maxn] ;
int ans[maxn],cnt ;
void dfs(int x)
{
    for(int i=0;i<v[x].size();i++) if(!vis[v[x][i]])
    {
        P &e=edge[v[x][i]] ;
        int to= e.x==x ? e.y : e.x ;
        vis[v[x][i]]=1 ;
        dfs(to) ;
    }
    ans[cnt++]=x ;
}
 
main()
{
    int m ;
    while(scanf("%d",&m)==1 && m)
    {
        edge.clear() ;
        for(int i=0;i<maxn;i++) v[i].clear() ;
        memset(vis,0,sizeof(vis)) ;
        for(int i=0;i<m;i++)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            edge.push_back((P){x,y}) ;
            v[x].push_back(i) ;
            v[y].push_back(i) ;
        }
        bool odd=0 ;
        int st=maxn ;
        for(int i=1;i<maxn;i++) if(!v[i].empty())
        {
            sort(v[i].begin(),v[i].end(),cmp) ;
            if(v[i].size()%2)
            {
                if(!odd) odd=1 , st=i ;
                else st=min(st,i) ;
            }
            else st=min(st,i) ;
        }
        cnt=0 ;
        dfs(st) ;
        for(int i=cnt-1;i>=0;i--) printf("%d\n",ans[i]) ;
        printf("\n") ;
    }
}