最后一句改为：但是本人很不理解为什么明明在缩点后建的图不可能有环，但是 dfs 会炸？
by liuzr156 @ 2023-12-10 12:59:41
@[liuzr156](/user/685987) 你缩完点之后建的图是会有重边的，拓扑重不重边无所谓，但是 dfs 重边了那你复杂度就指数级上升了。
by Ew_Cors @ 2023-12-10 13:02:08
也就是说不是死循环。
处理方法就是把新图的 vector 数组去个重。
by Ew_Cors @ 2023-12-10 13:03:01
哦去了重也不太行，你直接跑 dfs 不记忆化可以卡到指数级复杂度。
by Ew_Cors @ 2023-12-10 13:06:28
@[Ew_Cors](/user/180103)
为啥会卡到指数级啊
by liuzr156 @ 2023-12-10 13:09:40
@[liuzr156](/user/685987) 考虑这种建图方式：
```
(1->2)
(1->3)
(2->3)
(3->4)
(3->5)
(4->5)
...
```
这个时候你最后一个节点 $n$ 将会访问 $2^{\frac{n}{3}}$ 次。
by Ew_Cors @ 2023-12-10 13:14:40
@[Ew_Cors](/user/180103)
懂了，感谢大佬 /bx
所以有优化方法吗？
by liuzr156 @ 2023-12-10 13:17:45
@[liuzr156](/user/685987) 你看看这题能不能记忆化，我没仔细看题目。
by Ew_Cors @ 2023-12-10 13:22:54
@[Ew_Cors](/user/180103)
我改了一下 dfs 的方式可以过。
再次感谢！
by liuzr156 @ 2023-12-10 14:02:12