huangzelin 2023-07-17 17:48:07 2023-07-17 18:20:58 7 返回题目
所有点的出度为 1,这是内向基环树森林
问题转化为寻找图中最小的环
找最小环的方法有很多,讲讲我的:
先用拓扑排序去掉不在环上的点(因为环上的点入度永远不为 0, 所以不会被加入队列)
然后每个环跑一遍,找到最小的那个就可以了
时间复杂度 O (n)