ориентированный граф сильно связан

Question

В качестве входных данных приводится неориентированный граф G. Мне нужно сказать, можно ли направить каждое ребро графа G так, чтобы результирующий ориентированный граф был сильно связан.

Какой алгоритм я должен использовать?

Answer 1

Это эквивалентно определению, связан ли граф, и меньше bridge (где "bridge" - это ребро, так что, если вы удалите его, некоторые вершины станут отключенными).

Надеюсь, вам не составит труда выяснить, связан ли график. Для определения того, является ли он безмостным, вы можете использовать алгоритм поиска моста Тарьяна , который найдет мост тогда и только тогда, когда он существует.