找出图中所有环¶
一、问题¶
找出有向图中所有简单环（不重复经过节点）。
二、Tarjan 算法¶
找强连通分量（SCC），每个 SCC 内部就是环。
思路¶
DFS 时记录： - dfn：访问顺序。 - low：能回到的最早节点。
low == dfn 就是一个 SCC。
三、Johnson 算法¶
找所有简单环：
- 按编号顺序选起点。
- DFS，找从起点出发回到起点的环。
- 排除已访问节点。
四、复杂度¶
- Tarjan：O(V+E)。
- Johnson：O((V+E)(C+1))，C 是环数量。
五、举例¶
环：0→1→2→0。
六、应用¶
- 死锁检测。
- 依赖循环检测。
面试
知道 Tarjan 和 Johnson，能说思路就行。