algorithm - 找出有向图中的所有环？

Question

Tarjan 的强连通分量算法只能找到图中的基本循环或所有循环？

Answer 1

只要它在 O(V + E)（多项式时间）内运行，它就无法找到所有循环。如果可以的话，它可以在多项式时间内解决哈密顿循环问题，但这个问题是 NP 难的。