图-强连通分量

Question

有没有什么快速的方法来确定图中最大的强连通分量的大小？

我的意思是，比如，最明显的方法是确定每个SCC (我想可以使用两个DFS调用来完成)，然后遍历它们并取最大值。

我非常确定，如果我只需要组件的大小，并且只需要最大的一个，那么一定会有更好的方法，但我想不出一个好的解决方案。有什么想法吗？

谢谢。

Answer 1

让我用另一个问题来回答你的问题-

在不检查所有值的情况下，如何确定一个集合中的哪个值最大？

Answer 2

首先，你可以使用Tarjan's algorithm，它只需要一个DFS而不是两个。如果您清楚地理解该算法，SCC将形成一个DAG，并且此算法会以相反的拓扑排序顺序找到它们。因此，如果您对该图有一定的了解(如视觉表示)，并且您知道相对较大的SCC出现在DAG的末尾，那么一旦找到前几个SCC，您就可以停止该算法。