题解 P2731 【骑马修栅栏 Riding the Fences】

· · 题解

这题关于为什么不能在递归同时输出的问题很多题解都没有解释，唯一解释了的题解里面的图也挂了，所以我再来写一遍吧。
先给出两种输出路径方法：
错误的：

void dfs(int x)
{
    for(int i=1;i<=n;i++)if(a[i][x])
    {
        printf("%d\n",x);
        a[i][x]--;a[x][i]--;
        dfs(i);
    }
}
int main()
{
    //……
    printf("%d",&s);//s是起点
    dfs(s);
}

正确的： 

void dfs(int x)
{
    for(int i=1;i<=n;i++)if(a[i][x])
    {
        a[i][x]--;a[x][i]--;
        dfs(i);
    }
    p[size++]=x;
}
int main()
{
    //……
    dfs(s);
    for(int i=size-1;i>=0;i--)printf("%d\n",p[i]);
    return 0;
}

这里的关键问题就是前面所说的：为什么不能在递归的同时输出路径？
通过下面的例子可以很清楚地看出原因： 

4
1 3
1 4
3 4
1 2

图形：

3\
| 1-2
4/

可以发现，当用第一种方法时，程序会首先往2号点走，然后输出1 2，但直接往2号节点走就会被卡住。而出栈记录路径的方法就能避开这一点，往2走之后栈里的顺序是2 1，走完后会按2 1 3 4 1的方式正确地输出。由于是输出栈顶，所以2号节点也会最后输出。
那为什么出栈输出的方式适用于所有状态呢？
分两种情况讨论：
1.整个图是欧拉回路，递归时输出和出栈输出两种方法的效果一样，都采用的是贪心的方法遍历图。
2.整个图是欧拉路但不是欧拉回路，这时图可以被起点分为一个欧拉回路的子图与一个欧拉路的子图。当按出栈方法遍历时，假设欧拉路是上面的会在遍历完整张图前被卡住的情况：
如果欧拉回路的优先级低，程序会遍历完整张图才开始从最后一层函数返回，输出顺序是先欧拉回路再欧拉路；
如果欧拉路的遍历优先级低，则会先遍历欧拉路，当被卡住时返回，此时欧拉路上的节点都在栈的最低层，然后开始遍历欧拉回路，此时欧拉回路的节点都在栈顶部，所以输出顺序仍然是正确的欧拉回路再欧拉路。
所以，出栈的方法输出总是正确的。
这题也提醒了我们：即使做的是模板题，也要结合自己的想法思考算法的每一个细节，这样才能真正看懂算法，也能解决自己开始时对算法的不明白处。

最后上代码：（注释里的是错误范例） 

#include<cstdio>
#include<algorithm>
using namespace std;
int a[505][505];
int m,x,y,cnt[505],s=1024,n,p[1030],size;
void dfs(int x)
{
    for(int i=1;i<=n;i++)if(a[i][x])
    {
        //printf("%d\n",x);
        a[i][x]--;a[x][i]--;
        dfs(i);
    }
    p[size++]=x;
}
int main()
{
    for(scanf("%d",&m);m--;)
    {
        scanf("%d%d",&x,&y);
        a[x][y]++;a[y][x]++;//a[x][y]=a[y][x]=1;
        cnt[x]++;cnt[y]++;
        n=max(n,max(y,x));
        s=min(s,min(x,y));
    }
    for(int i=1;i<=n;i++)
        if(cnt[i]&1)
        {
            s=i;
            break;
        }
    //printf("%d\n",s);
    dfs(s);
    for(int i=size-1;i>=0;i--)printf("%d\n",p[i]);
    return 0;
}