Является ли сильно связная компонента 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.