SCC (Kosaraju)

O(n + m)

Strongly connected components of a directed graph in two passes: a postorder over the graph, then a sweep over the reverse graph in reverse postorder. Iterative, so deep graphs are safe. Component ids come out in topological order of the condensation, which is usually what the follow-up DP wants.

// use it on

CSES: Planets and Kingdoms ↗

Label each planet with its kingdom, which is literally the comp[] array this template produces.

// the code

struct SCC {  // comp[v] = component id, in topological order
    int n, comps = 0;
    vector<vector<int>> adj, radj;
    vector<int> comp;
    SCC(int n) : n(n), adj(n), radj(n), comp(n, -1) {}
    void add_edge(int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    void run() {
        vector<int> order, it(n, 0), st;
        vector<bool> seen(n, false);
        for (int s = 0; s < n; s++) {  // iterative postorder
            if (seen[s]) continue;
            seen[s] = true;
            st.push_back(s);
            while (!st.empty()) {
                int u = st.back();
                if (it[u] < (int)adj[u].size()) {
                    int v = adj[u][it[u]++];
                    if (!seen[v]) { seen[v] = true; st.push_back(v); }
                } else {
                    order.push_back(u);
                    st.pop_back();
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {  // sweep reverse graph
            if (comp[order[i]] != -1) continue;
            vector<int> q = {order[i]};
            comp[order[i]] = comps;
            while (!q.empty()) {
                int u = q.back();
                q.pop_back();
                for (int v : radj[u])
                    if (comp[v] == -1) { comp[v] = comps; q.push_back(v); }
            }
            comps++;
        }
    }
};

// more connectivity

SCC (Tarjan)Bridges & Articulation Points