USACO 骑马修栅栏 Riding the Fences

欧拉回路：对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；如果超过2个点的度为奇数，那么它就不存在欧拉路了。

题中说明至少有一个点，至少有一条欧拉回路。

如果有2个度数为奇数的点，那么就只能也这两个点之一为起点，另一个为终点。 题目要求我们输出的是进行进制转换之后最小的，所以我们要以最小的点做起点。

送上AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int temp[5000], edge[505][505], k;
int maxn, minn;
int min(int x,int y)
{
    return x < y ? x : y;
}
int max(int x,int y)
{
    return x > y ? x : y;
}
void dfs(int v)
{
    for(int i=minn;i<=maxn;i++)
       if( edge[v][i])
       {
             edge[v][i]--;
             edge[i][v]--;
             dfs(i);
       }
    temp[k++]=v;
}
int main()
{
    int first_point, second_point, i, edge_num;
    while(cin>> edge_num)
    {
        memset( edge,0,sizeof(edge));
        memset(temp,0,sizeof(temp));
        minn=505;
        maxn=0;
        k=0;
        for(i =0; i < edge_num; i ++)
        {
             cin>>first_point>>second_point;
             edge[first_point][second_point] ++;
             edge[second_point][first_point] ++;
             edge[first_point][0] ++; 
             edge[second_point][0] ++; 
             minn = min(minn,min(first_point,second_point));
             maxn = max(maxn,max(first_point,second_point));
        }
        for(i = minn; i <= maxn; i ++)
            if(edge[i][0]%2)
            {
                dfs(i);
                break;
            }
        if(i==maxn+1)    dfs(1);
        for(int j=k-1;j>=0;j--)
             printf("%d\n",temp[j]);
    }
    return 0;
}

USACO 骑马修栅栏 Riding the Fences

原文：https://www.cnblogs.com/zi-nai-boboyang/p/11437160.html