对于有n个节点的有向图G(V, E)，我想创建一个整数数组a，它的长度是n。如果从节点 1 到 2 有一条路径，则 a[1] <= a[2] , 如果它们在同一个强连接组件中 a[1] = a[2] ，如果没有从节点 2 到 3 的路径，我们有 a[2] > a[3] .
我觉得时间复杂度应该是O(n + m)，因为求强连通分量的时间复杂度就是它。但是我不确定如何为它输出一个数组，有人可以帮忙吗？谢谢。
最佳答案
一旦找到图中的每个强连通分量 (SCC)，就可以构建 condensation通过将每个 SCC 收缩为单个顶点来对图进行处理。凝聚是一个有向无环图，您可以在其中使用 topological sorting 对顶点进行编号。 .每一步都具有线性复杂度。
关于algorithm - 如何构建一个数组来呈现强连接组件中节点的关系？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48588261/