Solution

huangzelin 2023-07-17 17:48:07 2023-07-17 18:20:58 7 返回题目

所有点的出度为 1,这是内向基环树森林

问题转化为寻找图中最小的环

找最小环的方法有很多,讲讲我的:

先用拓扑排序去掉不在环上的点(因为环上的点入度永远不为 0, 所以不会被加入队列)

然后每个环跑一遍,找到最小的那个就可以了

时间复杂度 O (n)

{{ vote && vote.total.up }}