自动搬运

查看原文

来自洛谷，原作者为

	duoluoluo 她与残局皆遗憾

搬运于2025-08-24 22:06:34，当前版本为作者最后更新于2019-08-13 21:57:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

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

分析

• $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;
}