Разработать алгоритм времени O (| V | + | E |), который находит корневую вершину (или сообщает, что ее не существует) ориентированного графа

Question

Дан ориентированный граф G = (V, E).Корневая вершина в G - это вершина v такая, что любая другая вершина u в G достижима из v через направленный путь.Как разработать алгоритм времени O (| V | + | E |), который находит корневую вершину (или сообщает, что ее не существует).

Answer 1

Вот подход O (| V | + | E |):

1. Сначала мы можем объединить все узлы, которые принадлежат одному и тому же SCC (Сильно связанный компонент), к суперузлам и построить новый граф на основе этого, назовем его SCC-графом (он также известен как граф конденсации). , может быть сделано с помощью алгоритма Косараю в O (| V | + | E |))
2. Поскольку SCC-граф не может иметь циклы по определению, это DAG
3. Для каждого узла в SCC-графе мы можем вычислить его в градусах (количество ребер, направленных на него)
4. Теперь, если в SCC-графе более 1 узла с степенью 0, корня нет
5. Если в SCC-графе есть только один узел с степенью 0, то любой узел из исходного графа, являющийся частью узла SCC-графа с 0-градусом, может быть корневым