algorithm - 如何构建一个数组来表示强连通分量中节点的关系？

Question

对于具有n 个节点的有向图G(V, E)，我想创建一个整数数组a，其长度为n。如果存在从节点 1 到 2 的路径，则，如果它们在同一个强连通分量中，如果没有从节点 2 到 3 的路径，则有。a[1] <= a[2]a[1] = a[2]a[2] > a[3]

我觉得时间复杂度应该是O(n + m)，因为求强连通分量的时间复杂度就是它。但我不知道如何为它输出一个数组，有人可以帮忙吗？谢谢。

Answer 1

找到图的每个强连通分量 (SCC) 后，您可以通过将每个 SCC 收缩为单个顶点来构建图的凝聚。凝聚是一个有向无环图，您可以在其中使用拓扑排序对顶点进行编号。每一步都有线性复杂度。

Answer 2

Tarjan 的 SCC 算法几乎可以满足您的需求，您只需要一个额外的簿记步骤。

回想一下，Tarjan 的 SCC已经以拓扑排序的顺序一一输出强连通分量。也就是说，您只需将 SCC 的索引保存在与当前 SCC 的节点对应的所有单元格中。这已经是您想要的数组了。

根据图形的表示和实现，您可能希望保存N - idx在数组单元格中，其中N是找到的集群的总数。这是因为从本质上讲，您在哪个方向上遍历图形并不重要：带有反向箭头的图形的强连通分量是相同的。这取决于在您的具体实现中更容易和更快地访问什么。

Tarjan 的算法遍历图两次，运行时间为 O(|V| + |E|)。保留一个额外的数组不会给等式增加任何东西。