1 条题解
-
0
本题考察了DFS树的相关知识。
20pts
枚举所有情况。
+20pts
会发现树的情况下,所有边一定为桥,输出任意构造方案即可。
+20pts
会发现基环树的情况下,只需要把环上所有边定向后,变为环,剩下边任取即可。
100pts
以上两档部分分其实都在提醒我们从 这张图的角度看问题。
首先这个题目描述很像拆点,把每个点拆成入点和出点,每次操作就是给无向边定向。
然后考虑这样一个做法:把 和 连上一条双向边,然后在这个 个点 条边的无向图上跑 dfs,如果不是返祖边,那么就向上定向,否则向下定向。
证明一下这个做法的正确性。
首先如果一条边 在无向图上是桥,那么在原图上无论怎么连也都是桥。因为在原图上,只有这条边连接了 和 所在的连通块,所以它在原图上也一定是桥。
然后这么跑 dfs 相当于建出了很多强连通分量,如果 和 各有一条路径,删一条边一定不会影响连通性。
所以这样跑肯定是最小的。
时间复杂度:。
信息
- ID
- 221
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者