Худшее время поиска SCC с использованием DFS Kosaraju

Question

Алгоритм Косараджу гласит следующее:

#Input is graph G
1-define G_rev (links in reversed order)
2-Find the finishing times for G_rev using DFS
3-Run DFS for G in sequence based on finishing time

Время работы O(n+m), где n - количество вершин, а m - количество ребер. Если у меня есть полный граф G (все узлы соединены со всеми), число ребер равно m = n*n. Каково время работы в этом полном графе G? Когда я рассмотрю код DFS в (1), я начну с узла 1 (внешний цикл), и я буду посещать и завершать все остальные узлы. Внешний цикл будет проходить через все остальные узлы и обнаружит, что они закончили, и пропустить их. То же самое относится к (2). Кажется, я не буду посещать n * n ребер. Если G полон, есть только один SCC (весь граф), и время работы O(n+m) и m

Answer 1

Это правильно. Ваше время работы O(n+m) = O(n²).

Обратите внимание, что если вы заранее знаете, что ваш график завершен, запускать SCC на этом нет особого смысла.