UVA302 John's trip（欧拉回路）

欧拉回路

attention：

如果有多组解，按字典序输出。
起点为每组数据所给的第一条边的编号较小的路口
每次输出完额外换一行
保证连通性

每次输入数据结束后，先用入度判断图是否满足回路的条件。

满足的话跑一遍dfs即可。

需要注意格式。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;}

template <typename T> inline T max(T &a,T &b) {return a>b ?a:b;}

int mxd,st,to[][],tot,ans[],in[];

bool vis[];

inline void dfs(int x){

    for(int i=;i<=mxd;++i)

        if(!vis[i]&&to[x][i]){

            vis[i]=;

            dfs(to[x][i]);

            ans[++tot]=i;

        }

}

int main(){

    int u,v,w; bool ed=;

    while(scanf("%d%d",&u,&v)){

        if(!u&&!v){

            if(ed) break;

            bool ok=;

            for(int i=;i<=;++i) if(in[i]&) {ok=; break;} //入度判断

            if(ok){

                memset(vis,,sizeof(vis));

                dfs(st);

                while(tot-) printf("%d ",ans[tot--]); //逆序输出

                printf("%d\n",ans[tot--]);

            }

            else printf("Round trip does not exist.\n");

            memset(in,,sizeof(in));

            memset(to,,sizeof(to));

            ed=; st=mxd=;

            printf("\n"); //额外换行

            continue;

        }ed=;

        scanf("%d",&w);

        st= st ? st:min(u,v);

        mxd=max(mxd,w);

        to[u][w]=v; ++in[v];

        to[v][w]=u; ++in[u];

    }return ;

}