Алгоритм Косараджу гласит следующее:
#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 ‹ n*n . Это правильно?
