Косарайю для SCC: почему второй DFS надо запускать в порядке убывания времени завершения первого?
Реализую поиск компонент сильной связности алгоритмом Косарайю (два DFS). Первый DFS на исходном графе, второй — на транспонированном. Но почему именно порядок убывания времени завершения первого DFS критичен для второго прохода? Если запускать второй DFS в произвольном порядке — что сломается?
2 ответа
Алгоритм Косарайю:
- DFS по исходному графу G, выписываем вершины в порядке завершения (как в топсорте).
- Строим транспонированный граф G^T (все рёбра развёрнуты).
- DFS по G^T, перебирая вершины в порядке убывания времени завершения из шага 1. Каждый запуск DFS на шаге 3 выделяет ровно одну SCC.
vector<int> g[N], gt[N]; vector<bool> used; vector<int> order, comp;
int c;
void dfs1(int v){ used[v]=true; for(int u:g[v]) if(!used[u]) dfs1(u); order.push_back(v); }
void dfs2(int v){ comp[v]=c; for(int u:gt[v]) if(comp[u]==-1) dfs2(u); }
// dfs1 по всем; затем по order с конца: if(comp[v]==-1){ dfs2(v); c++; }
Почему порядок критичен. Рассмотрим конденсацию (DAG из SCC). Времена завершения обладают свойством: у SCC, которая в топологическом порядке конденсации стоит раньше (исток), максимальное время завершения больше, чем у SCC-стоков. То есть вершина с наибольшим fin лежит в «истоковой» SCC конденсации.
Когда мы запускаем DFS по G^T (рёбра развёрнуты!) из вершины с максимальным fin, в G^T эта истоковая SCC становится стоком — из неё по развёрнутым рёбрам нельзя уйти в другую SCC. Поэтому DFS по G^T обойдёт ровно её вершины и остановится — это и есть одна SCC.
Что сломается при произвольном порядке: если стартовать второй DFS не с максимального fin, можно начать с вершины, из которой в G^T достижимы несколько SCC, и DFS склеит их в одну — получите неверные, слишком крупные компоненты.
Сложность O(V+E), память O(V+E) (хранится и G, и G^T).
Короткая интуиция, чтобы запомнить: «убывание времени завершения» = топологический порядок конденсации. Мы обрабатываем SCC от истоков к стокам, но по транспонированному графу, где истоки и стоки меняются местами — поэтому из текущей стартовой SCC «не вытекает» в ещё не обработанные, и DFS аккуратно отрезает по одной компоненте.
Сравнение с Тарьяном (один DFS, без транспонирования): Косарайю проще доказывается и кодируется, но строит G^T (двойная память на рёбра) и делает два прохода. На практике на Codeforces оба укладываются; берите Тарьян, если память/скорость впритык, и Косарайю — если важнее ясность и нужно потом ещё работать с G^T. Грабля общая: рекурсия глубиной до V → на больших графах переписывайте оба DFS итеративно.