algorithm - 使用强连接组件进行拓扑排序以查找循环(​​有向图)

Question

据我所知，如果您有针对强连通组件的现成高效黑盒方法，那么进行拓扑排序的一种方法是:

(假设——没有自循环)

1. 运行强连接组件
2. 如果您有一个或多个大小 > 1 的分量，则此图有环。
3. 否则(图中只有 1 个大小的组件)这是一个 DAG，恭喜!
4. 如果是 DAG 运行拓扑排序，否则会提示你做不到。

不管效率如何，以上是一种“技术上正确”的拓扑排序方式吗？

我只是想确保我理解正确。

Answer 1

是的，这在技术上是正确的，因为没有自环的有向图是无环的(即拓扑可排序的)当且仅当所有强分量的大小都是 1。不过，最常见的拓扑排序将循环检测作为一个简单的副产品。