directed-acyclic-graphs - 在图论中，一个强连通分量SCC是否构成一个DAG？

Question

我试图解决一个问题来设计一种算法来确定直接图是否是半连通的。有人说可以通过对图中的每个 SCC 使用拓扑排序来完成。并且 SCC 保证是 DAG。但是，我认为 SCC 图一定是一个圆，为什么它是一个 DAG，因为 DAG 表示没有圆。

Answer 1

你误解了这个论点。

假设您有一个包含点的图

A1 <--> A2 <--> A3 --> B1 <--> B2 --> C1 <--> C2

和A1 A2 A3, B1 B2,C1, C2是 SCC。

然后你把A1 A2 A3它当作一个单点A。连接到其中之一的任何节点A1 A2 A3都被视为连接到A，从其中之一连接的任何节点A1 A2 A3都被视为连接自A。将点合并到B,C

于是就变成了A --> B --> C。保证这是一个 DAG。