题解 广度优先遍历

· · 题解

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

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

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