Компоненты сильной связности. Алгоритм Косараю-Шарира

• Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
• Транспонируем граф.
• Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").

vector<int> g[V_CNT], gR[V_CNT];
int u[V_CNT];
vector<int> order;

void dfs1(int v) {
    u[v] = 1;
    for (int i = 0; i < g[v].size(); i++)
        if (!u[g[v][i]])
            dfs1(g[v][i]);
    order.push_back(v);
}

void dfs2(int v, int k) {
    u[v] = k;
    for (int i = 0; i < gR[v].size(); i++)
        if (!u[gR[v][i]])
            dfs2(gR[v][i], k);
}

for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs1(i);
reverse(order.begin(), order.end());
for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
int k = 1;
for (int i = 0; i < V_CNT; i++)
    if (!u[order[i]])
        dfs2(order[i], k++);

Ссылки

• e-maxx.ru — Поиск компонент сильной связности, построение конденсации графа
• neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска компонент сильной связности
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
• Лахно А. П. Поиск в глубину и его применение
• algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs
• VisuAlgo — Graph Traversal
• CodeLibrary — Strongly connected components. Kosaraju's algorithm