关于欧拉回路的逆序输出问题

Posted by WHZ0325 on 2023-09-18, Viewed times

关于欧拉回路输出方案时，这么写是错误的：

1
2
3
4
5
6
7
8
void dfs(int x) {
    for(int i = 1; i <= 50; ++i) {
        if(g[x][i]) {
            --d[x]; --d[i]; --g[x][i]; --g[i][x];
            printf("%d %d\n", x, i); dfs(i);
        }
    }
}

而这样写则是正确的：

1
2
3
4
5
6
7
8
void dfs(int x) {
    for(int i = 1; i <= 50; ++i) {
        if(g[x][i]) {
            --d[x]; --d[i]; --g[x][i]; --g[i][x];
            dfs(i); printf("%d %d\n", i, x);
        }
    }
}

给出一组反例：

欧拉回路

如图，假若我们存的图在访问结点 3 时优先访问红边，其次访问黄边。

错误的方案会得到 $(1,2),(2,3),(3,1),(3,3)$，而正确的方案会得到 $(1,3),(3,3),(3,2),(2,1)$。