В чем разница между алгоритмом Тарьяна и алгоритмом Кана для топологической сортировки? Какой из них более эффективен?
Алгоритм сильносвязанных компонент Тарьяна , как указывает его название, не является алгоритмом топологической сортировки. Он производит только обратную топологическую сортировку сильно связанных компонентов.
Обычные алгоритмы топологической сортировки , включая алгоритм Кана, имеют сложность в O(|V|+|E|).
O(|V|+|E|)