这个图中有多少个强连通分量？

Question

考虑下图。我可以区分 4 个强连通分量，但它们是 5 个。 我错过了哪一个？另外，一个节点可以在多个组件中共享吗？

Answer 1

这 5 个组成部分是：

• 左上节点
• 右上节点
• 左下节点
• 右下节点
• 其余节点

你认为的组件实际上并不是组件，因为它们都可以展开到列表中的第 5 个组件。

请注意，无法扩展列出的组件，因为每个角节点都无法从其他任何地方到达（只有出边）或无法到达任何其他节点（只有入边）。因此，您不能将这些角添加到更大的组件，也不能将任何东西添加到角节点以使它们成为更大的组件。

根据定义，强连通分量是最大可能的（因此不可能进一步扩展它们），但在定义上没有相互交集的情况。然而，很容易证明以这种方式定义的组件不能有交集。