我们对边的最大权重值 C 进行二分,题目也就变成了:在边权小于等于 C 的边全部变成双向边时,是否存在一个节点能够到达所有的点。
通过 Kosaraju 我们可以知道,在进行第一遍 DFS 结束后,post_order 的最后一个点就是源点,我们只需要判断这个点能否到达所有点即可,可以通过检查遍历点的数量实现。
至于条件双向边的存储,可以使用邻接链表,链表内存一个结构体,存有这个边的目标点是什么,是不是反向边,边权是多少。当它是正向边时,它一定可以走,当它是反向边时,只有边权小于等于当前的检查值才可以走。
时间复杂度