Poj1041

题目大意：问该图中是否存在一条欧拉回路，若存在则输出其路径。

算法思路：存在欧拉回路很好判断，记录下每个点的度，因为是无向图，因此只需要每个点的度都是偶数即可。主要就是输出路径的问题，用普通的递归方法会超时，这里借鉴了网上的思路，详见代码。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
int maps[45][2000];

int h,a1,b1;
int a,b,num,e,len,sa,se,strcnt,stack_top;
bool isOver,visited[2000],isFirst,isGameOver;
int degree[45];
int ans[2000];
map<int,int>mp;

void dfs(int k) {
    for (int i = 1; i <= strcnt ;i++) {
        if (!visited[i] && maps[k][i]) {
            visited[i] = true;
            dfs(maps[k][i]);
            ans[stack_top++] = i;
        }
    }
}

void addNode(int x,int y,int numm)
{
    if(mp.find(x)==mp.end())
    {
        mp[x]=x;
    }

    if(mp.find(y)==mp.end())
    {
        mp[y]=y;
    }
    maps[x][num]=y;
    maps[y][num]=x;

    degree[x]++;
    degree[y]++;
    strcnt++;
}
int main()
{


    while(true)
    {
        isGameOver=false;
        mp.clear();
        memset(degree,0,sizeof(degree));
        memset(ans,0,sizeof(ans));
        memset(maps,0,sizeof(maps));
        isOver=isFirst=false;
        e=1;
        len=0;
        strcnt=1;
        scanf("%d%d",&a,&b);
        sa=a<b?a:b;
        if(a==0&&b==0)
            break;
        scanf("%d",&num);
        while(true)
        {
            addNode(a,b,num);

            scanf("%d%d",&a,&b);

            if(a==0&&b==0)
                break;


            scanf("%d",&num);


        }
        //printf("%d\n",len);
        //len=mp.size();
        for(int i=1; i<=44; i++)
        {
            if((degree[i])%2!=0)
            {
                isOver=true;
                break;
            }
        }

        if(!isOver)
        {
            memset(visited,false,sizeof(visited));
            stack_top=1;
            dfs(sa);
           for(int i=strcnt-1; i>1; i--)
                {
                    printf("%d ",ans[i]);
                }
                printf("%d\n",ans[1]);

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


    return 0;
}