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

Тогда вы относитесь A1 A2 A3 как единая точка A, Любой узел, соединяющийся с одним из A1 A2 A3 рассматривается как подключение к A, Любой узел, связанный с одним из A1 A2 A3 рассматривается как связанный с A, То же самое для объединения точек в B, C

Так стало A --> B --> C, Гарантируется, что это DAG.