poj 1041——John's trip

题意：求一个图的欧拉回路，将回路按照字典序最小输出

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn=2000;//dian
const int maxm=100000;//bian
bool vis[maxm];
int father[maxn];
vector<pair<int,int> > adj[maxn];

int getFather(int x)
{
    return x==father[x]?x:father[x]=getFather(father[x]);
}

void add(int x,int y,int z)
{
    adj[x].push_back(make_pair(z,y));
    adj[y].push_back(make_pair(z,x));
}

vector <int> path;

#define eid first
#define vtx second

void dfs(int u)
{
    for(int it=0;it<adj[u].size();++it)
    {
        if(!vis[adj[u][it].eid])
        {
            vis[adj[u][it].eid]=true;
            dfs(adj[u][it].vtx);
            path.push_back(adj[u][it].eid);
        }
    }
}


bool solve()
{
    for(int i=0;i<maxn;++i){
            father[i]=i;

    }

    for(int i=0;i<maxn;++i)
    {
        for(int j=0;j<adj[i].size();++j)
        {
            father[getFather(i)]=getFather(adj[i][j].second);
        }
    }
    int origin=-1;
    for(int i=0;i<maxn;++i)
    {
        if(adj[i].size())
        {
            if(adj[i].size()&1)return false;
            if(origin==-1)origin=1;
            if(getFather(i)!=getFather(origin))return false;
            sort(adj[i].begin(),adj[i].end());
        }
    }
    path.clear();
    memset(vis,0,sizeof(vis));
    if(origin!=-1)
    {
        dfs(origin);
    }
    reverse(path.begin(),path.end());
    return true;
}

int main()
{
  //  freopen("data.txt","r",stdin);
    while(1)
    {

        int x;int y;int z;
        scanf("%d%d",&x,&y);

        if(x==0&&y==0)break;
        for(int i=0;i<maxn;++i) adj[i].clear();
        scanf("%d",&z);
        add(x,y,z);
        while(scanf("%d%d",&x,&y))
        {
            if(x==0&&y==0)break;
            scanf("%d",&z);
            add(x,y,z);
        }

        if(solve())
        {
            for(int i=0;i<path.size();++i)
            {
                printf("%d ",path[i]);
            }
            printf("\n");
        }
        else printf("Round trip does not exist.\n");
    }
    return 0;

}