关于本题
查看原帖
关于本题
258178
Benzenesir楼主2023/7/16 22:29

RT,这篇题解中找出两个点后的 dfs 并不是断开了同一条边,而是断开了两条边,原因如下:

在第一次 DFS 中,若出现到 u的返祖边则退出,实际上是断掉了fa 到 u 的边

而在第二次 DFS 中,将 fa 设为 root 实际上是断开了 1-->2 这条边

但是实际上,这中写法的正确性是没有问题的,因为在搜索中,fa 和 u 不可能同时选取,而在第二次搜索中,因为倾定了 fa 不可以选,所以断哪条边都是无所谓的

但是这种写法并不是断了同一条边,所以不保证在其他题中不会出事

2023/7/16 22:29
加载中...