题解 P2731 【骑马修栅栏】

· · 题解

简述题意

给你F条边，叫你输出一种路径，使得该路径恰好经过每条边一次，并且路径的字典序最小。

这很明显是个欧拉路的题了，要想解决这道题，我们得先来了解一下欧拉路。

什么是欧拉路

在一幅图中，恰好经过每条边一次的路径叫做欧拉路。

什么是欧拉回路

如果一条欧拉路的起点与终点相同，我们就称这条路为欧拉回路。

欧拉路有什么性质

不难得出，一幅图如果存在欧拉路，则一定除起点和终点外，所有结点的度都为偶数，因为这些节点进来一遍，就一定会出去一遍，而起点只出不进，终点只进不出。

欧拉回路有什么性质

欧拉回路所有结点的度都为偶数。因为欧拉回路要求起点必须同时也是终点，所以对于任意的一点，都是进来一遍又出去一遍，度一定为偶数。

思路分析

知道了这些性质之后，我们该如何去解题呢？

不难得出，一幅图如果存在欧拉路，则欧拉路的起点一定是度数为奇数的点，我们管这类点叫做奇点。而如果存在欧拉回路，则起点可以为任意点，因为题目要求字典序最小，所以起点为1号结点。

所以我们现在要做的就是找到这个起点，然后进行一遍 dfs 就行了。

如何找起点呢？

我们令 e_i 表示结点i的度，则每次读入一条从结点 u 到结点 v 的栅栏， e_u++ ， e_v++。读完所有栅栏之后，遍历一遍所有的结点，若 e_i%2==1，则返回结点 i 即为起点，若未找到一个满足条件的 e_i ，则返回结点1为起点。

最后 dfs 一遍，记录路径，输出即可。

注意：该题有重边

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int farm[550][550];//farm[i][j]表示i到j之间有几条边 
int e[550];//e[i]表示i结点的度 
int out[1050],h=0;//out记录输出序列，h为out的下标 
int maxn=0;//最大结点，因输入中未告知，所以要自己找 
int f;//栅栏数 
int find_ji(){//找奇点 
for(int i=1;i<=maxn;i++)
    if(e[i]%2==1)
        return i;
return 1;//没有则返回1 
}
void dfs(int now){
    for(int i=1;i<=maxn;i++)
        if(farm[now][i]){
            farm[now][i]--;//走过一条边 
            farm[i][now]--;
            dfs(i);//继续递归i结点 
        }
    out[++h]=now;//记录输出序列 
}
int main()
{
    memset(farm,false,sizeof(farm));
    memset(e,0,sizeof(e));
    scanf("%d",&f);
    int a,b;
    for(int i=1;i<=f;i++){
        scanf("%d%d",&a,&b);
        farm[a][b]++;//a和b之间的边数++ 
        farm[b][a]++;
        e[a]++;//a，b的度++ 
        e[b]++;
        maxn=max(maxn,max(a,b));//找最大结点 
    }
    int ji=find_ji();
    dfs(ji);//从奇点开始 
    for(int i=h;i>=1;i--)//因为我们是倒序记录路径的，所以要倒序输出 
        printf("%d\n",out[i]);
    return 0;
}