学步园

题目链接:   USACO 3.3.1

题目大意:   给出无向图，可能有重边

                  输出最小顶点字典序的欧拉通路路径

解题思路:   无向欧拉回路的判断方法，若不存在奇数度点或存在两个奇数度点

                  则存在欧拉路径，至于重边可以这样处理Edge[a][b]++

                  PS:欧拉路径的问题要记得判断图是否联通

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 502
int S,E,n,m,edge[MAX][MAX],Du[MAX],ans[2000],k;

void DFS(int start)
{
    int i;
    for(i=S;i<=E;i++)
    {
        if(edge[start][i]>=1)
        {
            edge[start][i]--;
            edge[i][start]--;
            DFS(i);
        }
    }
    ans[++k]=start;
}

int main()
{
    int i,a,b,start,num;
    while(scanf("%d",&n)!=EOF)
    {
        num=start=k=0;
        S=0x3f3f3f3f;E=0;
        memset(edge,0,sizeof(edge));
        memset(Du,0,sizeof(Du));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a][b]++;
            edge[b][a]++;
            if(a<S) S=a;if(b<S) S=b;
            if(a>E) E=a;if(b>E) E=b;
            Du[a]++;Du[b]++;
        }
        int pd=0;
        start=S;
        for(i=S;i<=E;i++)
        {
            if(Du[i]%2==1)
            {
                num++;
                if(start==S&&!pd)
                    start=i,pd=1;
            }
        }
        if(num==0||num==2)
            DFS(start);
        else
            printf("No\n");
        for(i=k;i>=1;i--)
            printf("%d\n",ans[i]);
    }
}