Comments 2
Конец 2024 года, а я тут оставляю первый комментарий.
Спасибо тебе, @bash_mac, очень выручил!!! Это лучшее описание алгоритма Косарайю в рунете на текущий момент.
В википедии, кстати, вообще некорректно написано:
Инвертируем дуги исходного ориентированного графа.
Запускаем поиск в глубину на этом обращённом графе, запоминая, в каком порядке выходили из вершин.
Запускаем поиск в глубину на исходном графе, в очередной раз выбирая не посещённую вершину с максимальным номером в векторе, полученном в п.2.
Полученные из п.3 деревья и являются сильно связными компонентами.https://ru.wikipedia.org/wiki/Алгоритм_Косарайю
Впрочем не в первый раз вижу математические косяки в википедии :(
Рад, что статья пригодилась)
По поводу Википедии -- у неё алгоритм тот же с точностью до шага инвертирования. По 3 лемме неважно, на исходном графе мы проставляем метки, или на инвертированном. Главное -- чтобы во второй DFS мы шли по меткам в обратном порядке в графе, который инвертирован относительно первого прохода DFS.
У меня первый DFS по исходному графу, а воторой -- по инвертированному.
У Википедии первый DFS по инвертированному, второй -- по исходному.
Алгоритм Kosaraju по полкам