题解 P5049 【旅行（数据加强版）】

题意

题意很简单，即在一张图上一边跑一边记录当前所在节点的大小，不能走已经经过的点，但是可以回溯，最后输出字典序最小的编号序列。

分析

• m = n - 1

这种情况不用多说，直接跑一遍DFS就行啦！

• m = n

大家应该很清楚这个情况会使图中出现一个环。

那要怎么解决呢？想想是不是你在这个环上跑到一半，另一半通过回溯到你刚到这个环的起点，再接着DFS就行了。

举个样例2的例子：

很明显2 - 3 - 4 - 5是图上的环。

最开始从1节点出发，那么3就是我们第一次到这个环的起点。

接着我们向2走，之后便回溯到起点3，3再向4走，最后跑完整张图就行了，因为接下来就没有环需要我们特殊处理了。

这个过程应该很好理解，现在我们知道m = n情况下只需要处理在环上的点，其他的点还是像m = n - 1一样DFS就好了，同时如果在环上回溯之后（如上图2回溯到3），剩下的过程也不需要特殊处理了。

那么现在的关键就是解决在环上的特殊处理。

我们把在环上的点分成三种情况：

一、其出边为环上的那个点编号是其所有未被访问的出边中最小的，如下图。

从1出发经过2到达3，此时从3出发能访问的出边有4, 6, 7，其中4是环上的点，同时也是最小。

二、其出边为环上的那个点编号是其所有未被访问的出边中不是最大也不是最小的，如下图。

此时6是环上的点，但不是最大也不是最小的出边。

三、其出边为环上的那个点编号是其所有未被访问的出边中最大的，如下图。

此时7是最大的出边也是环上的点。

对于第一种情况（见下图）：

由于我们现在在3这个节点，如果我们回溯的话，6和7就永远也到不了了，所以在回溯之前要先把6和7走完，相比6和7，走4显然会更优。

所以第一种情况不需要回溯，继续在环上走就行了。

对于第二种情况（见下图）：

同样还是在3节点，这次显然我们要先走4，但是走完4还是得走6节点，同样也不需要回溯。

对于第三种情况（见下图）：

这时候很明显是要回溯的了。

需要注意的是回溯之前要先把4和6先走了再回溯（原因上面刚讲过了）。

但是，如果我们换张图，还需要回溯吗？（见下下图）

这张图中，我们假设当前还是在3节点，6是其出边中最大且在环上的点。

这时候需不需要回溯呢？很显然不需要

因为回溯之后回到了2，2继续走的话是走到了7，显然走6比起7更优。

总结一下，我们在环上走的时候，只有当其出边中，为环上的那个点编号最大，且比回溯后第一个走的点还大，这时候才回溯，其他时候就正常跑DFS。

因此在代码上我用了flag来标记是否需要回溯，用tmp记录当前节点中第一个比环上的出边那个节点还要大的节点，以便后面判断是否回溯时比较。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int N = 500010;
int n, m, vis[N], ans[N], cnt, f[N], rings[N], flag, tmp, temp, head[N], ver[N << 1], nex[N << 1], tot;
struct Node {
    int x, y;
}node[N << 1];
void add (int x, int y) {
    ver[++ tot] = y;
    nex[tot] = head[x];
    head[x] = tot;
}
bool cmp (Node a, Node b) {
    return a.y > b.y;
}
inline int read () {
    int res = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        res = (res << 3) + (res << 1) + (ch - 48);
        ch = getchar();
    }
    return res;
}
void dfs (int x) {
    vis[x] = 1;
    ans[++ cnt] = x;
    for (int i = head[x]; i; i = nex[i]) {
        int y = ver[i];
        if (!vis[y])
            dfs(y);
    }
}
void dfsRing (int x, int fa) {
    if (flag) return;
    if (f[x] == 0) {
        f[x] = fa;
    }else if (f[x] != fa) {
        while (fa != x) {
            rings[fa] = 1;
            fa = f[fa];
        }
        rings[x] = 1;
        flag = 1;
        return;
    }
    for (int i = head[x]; i; i = nex[i]) {
        int y = ver[i];
        if (y == fa) continue;
        dfsRing(y, x);
    }
}
void sDfs (int x) {
    vis[x] = 1;
    ans[++ cnt] = x;
    if (rings[x]) { //判断x是否在环上 
        int flag = 0;
        for (int i = head[x]; i; i = nex[i]) {
            if (temp) break; //temp标记环上的回溯是否执行过了，因为一旦执行过环上的回溯，那么后面就不需要在环上回溯，只需正常跑DFS即可 
            int y = ver[i];
            if (vis[y]) continue;
            if (rings[y]) {
                i = nex[i];
                while (vis[ver[i]]) //已经被访问过的节点跳过 
                    i = nex[i];
                if (i) //i不为0即环上的出边不是最大的出边 
                    tmp = ver[i]; //tmp记录第一个比环的出边大的那个点 
                else if (y > tmp) { //环上的出边是最大的出边且比我们回溯后第一次要走的节点还大 
                    flag = 1;
                    temp = 1;
                }
                break;
            }
        }
        for (int i = head[x]; i; i = nex[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            if (rings[y] && flag) continue; //flag = 1，因此回溯，不再走环上的出边 
            sDfs(y);
        }
    } else {
        for (int i = head[x]; i; i = nex[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            sDfs(y);
        }
    }
}
int main () {
    n = read();
    m = read();
    for (int i = 1; i <= m; i ++) {
        int u = read(), v = read();
        node[i].x = u;
        node[i].y = v;
        node[i + m].x = v;
        node[i + m].y = u;
    }
    sort(node + 1, node + 2 * m + 1, cmp);
    for (int i = 1; i <= 2 * m; i ++)
        add(node[i].x, node[i].y);
    if (m == n - 1) {
        dfs(1);
        for (int i = 1; i <= n; i ++)
            printf("%d ", ans[i]);
    }else {
        dfsRing(1, 1); //一开始先找出所有在环上的点 
        flag = 0;
        tmp = 0x3f3f3f3f;
        sDfs(1);
        for (int i = 1; i <= n; i ++)
            printf("%d ", ans[i]);
    }
    return 0;
}