一个奇怪的想法,关于欧拉回路

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

Glax712124 @ 2024-11-25 11:37:30

众所周知,P2731 [USACO3.3] 骑马修栅栏 Riding the Fences是欧拉回路的板子题。

这是题解区第一篇@EarthGiao大佬的题解代码:

//防伪标识
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int map[10001][10001];//记录两个点之间的路径个数 
int du[10001];//辅助记录奇点 
int lu[10001];//记录路径 
int n,x,y,js=0;
int maxn=0;
void find(int i)//
{
    int j;
    for(j=1;j<=maxn;++j)//而且这里不是n而是maxn因为n不是点的个数而是下面有多少行 
    {
        if(map[i][j]>=1)
        {
            map[i][j]--;//删去边一次吗避免重复 
            map[j][i]--;//z这里和一笔画不一样这里是累减而一笔画直接变成0 
            find(j);
                       (******①******)
        }
    }
    lu[++js]=i;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        map[x][y]++;
        map[y][x]++;
        du[x]++;
        du[y]++;//记录出现的次数 
        maxn=max(maxn,max(x,y));
    }
    int start=1;//默认奇点是1 
    for(int i=1;i<=maxn;++i)
    {
        if(du[i]%2)//找到奇点 
        {
            start=i;//记录奇点
            break;//然后结束循环 
        }
    }
    find(start);//从奇点开始找 
    for(int i=js;i>=1;i--)
    {
        printf("%d\n",lu[i]);//挨个输出路径并且换行 
    }
    return 0;
}

为什么在①这个地方加个break就错了呢?

理论上没有问题啊!

求反例,谢谢大佬。


by zhangshiwei @ 2024-11-27 14:35:08

考虑这样一张图,边为:

1 2,2 3,3 2,3 1,2 4,3 4

DFS访问顺序为:

1->2->3->1->2->4->3

这显然不是合法的

但是DFS的返回顺序(括号中)为:

1(7)->2(6)->3(5)->1(1)->2(4)->4(3)->3(2)

依次得到序列

1->3->4->2->3->2->1

恰好是一个欧拉回路


by zhangshiwei @ 2024-11-27 14:38:23

也就是说,如果break,DFS访问到

1->2->3->1(无更多边)

就结束了,因此错误


|