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(无更多边)
就结束了,因此错误