Kosaraju's Algorithm

Kosaraju's algorithm is a classic method for finding strongly connected components (SCCs) in a directed graph. A strongly connected component is defined as a maximal set of vertices such that every vertex is reachable from every other vertex within the set. In other words, for any two vertices u and v in a strongly connected component, there exist directed paths u→...→v and v→...→u.

Algorithm Steps:

1. Perform a DFS on the original graph to compute a finishing order for all vertices.
2. Construct the transpose (reversed) graph by reversing every edge.
3. Process the vertices in decreasing order of their finishing times. Run DFS on the transpose graph, collecting one SCC per traversal.

Complexity: Kosaraju's algorithm runs in O(V + E) time and uses O(V + E) memory.

Problems Solvable with Kosaraju's Algorithm

These problems from Codeforces and AtCoder apply Kosaraju's algorithm or SCC computation techniques.

Intermediate-Level Problems

Domino Principle (Codeforces 1312D)

Goal: Determine minimum dominoes needed to topple all by pushing some of them initially. SCCs can be used to find domino groups.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> g, rg;
vector<bool> visited;
stack<int> st;

void dfs1(int u) {
    visited[u] = true;
    for (int v : g[u])
        if (!visited[v]) dfs1(v);
    st.push(u);
}

void dfs2(int u) {
    visited[u] = true;
    for (int v : rg[u])
        if (!visited[v]) dfs2(v);
}

int main() {
    int n, m;
    cin >> n >> m;
    g.resize(n); rg.resize(n);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        g[x].push_back(y);
        rg[y].push_back(x);
    }

    visited.assign(n, false);
    for (int i = 0; i < n; ++i) if (!visited[i]) dfs1(i);

    visited.assign(n, false);
    int ans = 0;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (!visited[u]) {
            dfs2(u);
            ans++;
        }
    }
    cout << ans << endl;
}

Calling Circles (UVa 247 - used in many online judges)

Goal: Identify groups where everyone can reach everyone else (SCCs).

#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <set>
using namespace std;

map<string, int> name2id;
vector<string> id2name;
vector<vector<int>> g, rg;
vector<bool> vis;
stack<int> st;

void dfs1(int u) {
    vis[u] = true;
    for (int v : g[u]) if (!vis[v]) dfs1(v);
    st.push(u);
}

void dfs2(int u, set<int>& comp) {
    vis[u] = true;
    comp.insert(u);
    for (int v : rg[u]) if (!vis[v]) dfs2(v, comp);
}

int main() {
    int n, m; cin >> n >> m;
    g.resize(n); rg.resize(n);
    for (int i = 0; i < m; ++i) {
        string a, b;
        cin >> a >> b;
        if (name2id.count(a) == 0) {
            name2id[a] = name2id.size();
            id2name.push_back(a);
        }
        if (name2id.count(b) == 0) {
            name2id[b] = name2id.size();
            id2name.push_back(b);
        }
        int u = name2id[a], v = name2id[b];
        g[u].push_back(v);
        rg[v].push_back(u);
    }

    vis.assign(n, false);
    for (int i = 0; i < n; ++i) if (!vis[i]) dfs1(i);
    vis.assign(n, false);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (!vis[u]) {
            set<int> comp;
            dfs2(u, comp);
            for (int id : comp) cout << id2name[id] << " ";
            cout << endl;
        }
    }
}

Hard-Level Problem

Reachability Queries (Codeforces 427C)

Goal: Find the minimal cost to cover all SCCs and count the number of ways to do it using the smallest node cost from each SCC.

#include <iostream>
#include <vector>
#include <stack>
#include <climits>
using namespace std;

const int MOD = 1e9+7;

vector<vector<int>> g, rg;
vector<int> cost;
vector<bool> vis;
stack<int> st;

void dfs1(int u) {
    vis[u] = true;
    for (int v : g[u]) if (!vis[v]) dfs1(v);
    st.push(u);
}

int dfs2(int u, int& minCost, int& count) {
    vis[u] = true;
    if (cost[u] < minCost) {
        minCost = cost[u];
        count = 1;
    } else if (cost[u] == minCost) count++;
    for (int v : rg[u])
        if (!vis[v]) dfs2(v, minCost, count);
    return 0;
}

int main() {
    int n; cin >> n;
    cost.resize(n);
    for (int i = 0; i < n; ++i) cin >> cost[i];

    g.resize(n); rg.resize(n);
    int m; cin >> m;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        g[u].push_back(v);
        rg[v].push_back(u);
    }

    vis.assign(n, false);
    for (int i = 0; i < n; ++i)
        if (!vis[i]) dfs1(i);

    vis.assign(n, false);
    long long totalCost = 0, ways = 1;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (!vis[u]) {
            int minCost = INT_MAX, count = 0;
            dfs2(u, minCost, count);
            totalCost += minCost;
            ways = (ways * count) % MOD;
        }
    }
    cout << totalCost << " " << ways << endl;
}