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

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

vector<vector<int>> g(n), gr(n);
vector<int> visited(n);
vector<int> order;

void dfs1(int v) {
    visited[v] = 1;
    for (int to : g[v])
        if (!visited[to])
            dfs1(to);
    order.push_back(v);
}

void dfs2(int v, int component) {
    visited[v] = component;
    for (int to : gr[v])
        if (!visited[to])
            dfs2(to, component);
}

for (int v = 0; v < n; v++)
    if (!visited[v])
        dfs1(v);
reverse(order.begin(), order.end());

fill(visited.begin(), visited.end(), 0);

int componentsCount = 0;
for (int v : order)
    if (!visited[v])
        dfs2(v, ++componentsCount);

Построение конденсации:

unordered_map<int, vector<int>> g, gr, gc; 
unordered_set<int> visited;
vector<int> order;

void dfs1(int v) {
    visited.insert(v);
    for (int to : g[v]) {
        if (!visited.count(to))
            dfs1(to);
    }
    order.push_back(v);
}

unordered_map<int, int> scc;

void dfs2(int v, int component) {
    visited.insert(v);
    scc[v] = component;
    for (int to : gr[v]) {
        if (!visited.count(to))
            dfs2(to, component);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        string a, b;
        cin >> a >> b;
        g[a].push_back(b);
        gr[b].push_back(a);
    }
   
    for (int v = 0; v < n; v++) {
        if (!visited.count(v))
            dfs1(v);
    }
    reverse(order.begin(), order.end());

    visited.clear();
    int sccN = 0;
    for (int v : order) {
        if (!visited.count(v))
            dfs2(v, sccN++);
    }

    for (int v = 0; v < n; v++) {
        for (int to : g[v])
            if (scc[v] != scc[to])
                gc[scc[v]].push_back(scc[to]);
    }
}

Ссылки

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