自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:49:17，当前版本为作者最后更新于2023-08-03 21:42:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

已经把以 $1$ 为根的 bfs 树给定了，那么对于原图中的一条非树边，如果它连接的是深度相同的节点那么这条边无所谓，因为无论如何它都不会成为树边，如果它连接的是深度不同的节点，那么必然连接的是相邻两层节点，否则无解，不妨设连接的是 $u,v$，且 $u$ 在 $v$ 的上一层，且 $w$ 是 $v$ 的父亲，$u,v$ 的 lca 是 $z$，其中 $z$ 往下靠近 $u$ 的是 $1$ 号边，而靠近 $v$ 的是 $2$ 号边，如下图。

那么这其实说明 $v$ 这个点被 $w$ 给“抢”掉了，或者说 $w$ 应该在队列中排在 $u$ 的前面，进一步而言就是 $2$ 号边应该在 $1$ 号边的前面，并且容易发现这是充要的。

对于所有这样的非树边都有一个这样的偏序关系，找到一个拓扑序输出即可。