Использование обхода в глубину для поиска компонент сильной связности

Постановка задачи

Дан ориентированный граф G. Требуется найти в этом графе компоненты сильной связанности.

Алгоритм

Данная задачи решается с помощью поиска в глубину в 3 этапа:

1. Построить транспонированный граф
2. Выполнить в транспонированном графе поиск в глубину и найти f[u] - время окончания обработки вершины u
3. Выполнить поиск глубину в G, перебирая вершины во внешнем цикле в порядке убывания f[u]

Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа G Так как компоненты сильной связности исходного и транспонированного графа совпадают, то первый поиск в глубину для нахождения f[u] можно выполнить на графе G, а второй - на транспонированном

Доказательство

Рассмотрим пару вершин s и t. Если вершины s и t взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня. Теперь докажем, что если s и t находятся в одном дереве поиска, то они являются сильно связанными. Пусть r - корень этого дерева. Тогда s достижима из r, из чего следует, что в обратном графе r достижима из s. Но r имеет большее время окончания обработки f[r] > f[s], из чего следует что в обратном графе существует путь из r в s. Тогда в исходном графе существуют пути как из s в r, так и из r в s, т.е. r и s сильно связаны. Те же рассуждения доказывают, что t и r сильно связаны, из чего следует что t и s также сильно связаны.

Пример реализации

vector<vector<int>> g, g1; vector<int> color, ord, component; int col;

void dfs(int & v) {

   color[v] = 1;
   for (unsigned i = 0; i < g[v].size(); ++i)
   {
       if (color[g[v][i]] == 0)
           dfs(g[v][i]);
   }
   ord.push_back(v);

}

void dfs2(int & v) {

   color[v] = col;
   for (unsigned  i = 0; i < g1[v].size(); i ++ )
   {
       if (color[g1[v][i]] == 0)
           dfs2(g1[v][i]);
   }

}

int main() {

   ...
   for (int i = 1; i <= n; ++i)
   {
       if (color[i] == 0)
           dfs(i);
   }
   col = 1;
   for (int i = ord.size(); i > 0; --i)
   {
       if (color[ord[i - 1]] == 0)
           dfs2(ord[i - 1]), col++;
   }

}