Найти самый достижимый узел от каждого узла

Question

У меня есть ориентированный граф G (V, E). G может содержать циклы. Каждый v начинается со значения n [v]. Давайте назовем S {v} всеми вершинами, достижимыми v в G. Для каждого v мне нужно обновить n [v] с помощью max (n [u]), u∈S {v}.

I я пытался использовать Quick-Union со сжатием пути , но я не могу, потому что G - это ориентированный граф.

Можно использовать DFS на каждом узле, но сложность будет O (V (V + E)) в худшем случае.

Есть ли лучший способ приблизиться к нему (возможно, используя топологическую сортировку, переходное сокращение или сильно связанные компоненты)?

Answer 1

Да, есть лучший способ O (V + E):

1. Найти все сильно связанные компоненты (алгоритмы Кадане или Тарьяна) и сохранить max_n[v] для каждой вершины в компоненте
2. построить новый график из сильно связанных компонентов
3. новый график - это DAG
4. использовать DP для вычисления требуемых значений для каждого компонента (для DAG его можно либо сверху вниз с помощью DFS, либо снизу вверх с Каном)