骑马修栅栏-题解

查看原题请戳这里

我做的第一道欧拉路径的题

说实话，这就一板子题…… 欧拉路径不会求的戳这里。 直接上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;
int n,m,x,y,head[1200],cnt,map[1030][1030],d[1030],begin,s[1030],t;
void dfs(int k)
{
    for(register int i = 1; i <= n; i++)
    {
        if(map[k][i] > 0)
        {
            map[k][i] –;
            map[i][k] –;
            dfs(i);
        }
    }
    s[++t] = k;
}
int main()
{
    scanf(“%d”,&m);
    for(register int i = 1; i <= m; i++)
    {
        scanf(“%d%d”,&x,&y);
        map[x][y] ++;
        map[y][x] ++;
        n = max(n,x);
        n = max(n,y);
        d[x] ++;
        d[y] ++;
    }
    for(register int i = 1; i <= n; i++)
    {
        if(d[i] % 2 == 1)
        {
            begin = i;
            break;
        }
    }
    if(begin == 0) begin = 1;
    dfs(begin);
    for(register int i = t; i >0; i–) printf(“%d\n”,s[i]);
    printf(“\n”);
    return 0;
}