jingkongwanglimiaoa @ 2020-08-20 13:44:34
这是一道欧拉板子题尽管是模板但本蒟蒻还是一如既往的迷惑呢
经过长时间地坚持看题解,我终于A了这道题
但本蒟蒻还是有个问题没搞明白,先贴两段代码
1.正确AC代码
void dfs(int x)//深搜
{
for (int i = 0;i <= maxn;i++)//maxn指最大数值的点
if (e[x][i])
{
e[x][i]--;//删边 ,e数组表示两个点有几条边
e[i][x]--;
dfs(i);
}
q[++hd] = x; //hd为队尾,x入队
}
2.不正常WA两个点代码
void dfs(int x)//深搜
{
q[++hd] = x; //hd为队尾,x入队
for (int i = 0;i <= maxn;i++)//maxn指最大数值的点
if (e[x][i])
{
e[x][i]--;//删边
e[i][x]--;
dfs(i);
}
}
两个代码几乎一模一样,就改了一行代码的顺序,它就wa了两个点,输出那里我一个倒序一个正序是莫得问题的,真是个玄学错误
奇妙蒟蒻遇玄学错误
by mot1ve @ 2020-08-20 14:03:37
这个图 如果从1出发的话,终点一定是3,你那样存,从1出发显然会把3的位置存错。而递归求的话就会把3放到栈底部。这样保证3是终点。
by mot1ve @ 2020-08-20 14:04:24
我画的这个图其实是欧拉路径 不是欧拉回路 但其实原理一样的 你错误的点在这个图也适用
by jingkongwanglimiaoa @ 2020-08-20 19:48:45
啊我懂了,如果我想要把入队操作放前面的话就要加上回溯,然而加了回溯后会
by jingkongwanglimiaoa @ 2020-08-20 19:49:39
@kuoluo03 谢谢神犇