Strongly Connected Components — Tarjan's Algorithm

A strongly connected component is a maximal group of vertices where every vertex reaches every other by directed paths. Condensing SCCs turns any directed graph into a DAG, useful for dependencies, reachability reductions and 2-SAT. Tarjan finds all SCCs in one DFS pass using discovery indices, low-link values and an active stack. It is an alternative to two-pass Kosaraju, not the same low-link algorithm as undirected bridge detection.

Prerequisites: Depth-first search; directed graphs; existing SCC lesson. Difficulty: Advanced. Review: Depth-first search, Strongly connected components.

Build the idea

1. 1. Distinguish three kinds of state

   index[v] is the fixed discovery time, initially −1. low[v] summarizes how far back v’s still-active DFS region can connect. onStack[v] means v belongs to an SCC not yet extracted. A vertex may have finished its recursive call but still be on the SCC stack, so onStack is not equivalent to “currently executing recursion.” component[v] is assigned only when extraction occurs.

2. 2. Process tree and active edges differently

   When u is undiscovered, recurse and propagate low[u] back into low[v]. When u is already discovered AND on the SCC stack, reduce low[v] using index[u]. If u has been popped into a completed component, ignore that edge for low-link purposes. That completed SCC cannot help v belong to the same unresolved component. Do not reuse an undirected rule that simply skips the parent edge; directed reverse edges may be genuine cycle evidence.

3. 3. Recognize a component root

   After all outgoing edges have been examined, low[v]==index[v] means v is the earliest discovery of its unresolved component. Pop the SCC stack through v and give every popped vertex one component ID. No unresolved descendant can connect back earlier than v, and all popped vertices are mutually linked through the DFS/active paths. If low[v] is smaller, leave v on the stack for an earlier root to extract.

4. 4. Trace the example

   Edges 1→2→3→1 form one SCC. Edge 3→4 leads to the SCC {4,5} through 4→5 and 5→4, and 5→6 leads to singleton {6}. DFS discovers all six before returning; it first pops {6}, then {4,5}, then {1,2,3}. The program labels components in extraction order, giving IDs [3,3,3,2,2,1]. These numeric labels are incidental; equality of labels identifies membership.

5. 5. Build what comes next

   Scan each original edge u→v and add component[u]→component[v] when the IDs differ. The resulting condensation has no directed cycle: a cycle of components would make them mutually reachable and hence one component. This implementation extracts sink-side components before source-side ones; do not copy the earlier 2-SAT comparison without adjusting its SCC ordering convention. Deduplicate condensation edges only when a later task needs it.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    if(!(cin>>n>>m)){
        return 0;
    }
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
    }
    vector<int>index(n+1,-1),low(n+1),component(n+1),stack;
    vector<char>onStack(n+1,false);
    int timer=0,count=0;
    function<void(int)>dfs=[&](int v){
        index[v]=low[v]=timer++;
        stack.push_back(v);
        onStack[v]=true;
        for(int u:graph[v]){
            if(index[u]==-1){
                dfs(u);
                low[v]=min(low[v],low[u]);
            }
            else if(onStack[u]){
                low[v]=min(low[v],index[u]);
            }
            // Already extracted vertices cannot lower this SCC's low-link.
        }
        if(low[v]==index[v]){
            ++count;
            for(;;){
                int u=stack.back();
                stack.pop_back();
                onStack[u]=false;
                component[u]=count;
                if(u==v){
                    break;
                }
            }
        }
    };
    for(int v=1;v<=n;++v){
        if(index[v]==-1){
            dfs(v);
        }
    }
    cout<<count<<'\n';
    for(int v=1;v<=n;++v){
        cout<<component[v]<<(v==n?'\n':' ');
    }
}

Complexity analysis

O(V+E) time: each vertex enters and leaves the SCC stack once, and each directed edge is examined once. O(V+E) total memory includes adjacency plus O(V) arrays, SCC stack and recursive stack. No transpose graph is needed. Deep directed chains may exceed the C++ recursion stack; the program targets moderate depths, and very large instances need explicit DFS frames.

Example input and output

Read n m and m directed edges u v, labels 1..n, n≥1. Print the number of SCCs and one component ID per vertex. IDs follow this program’s DFS extraction order; another valid solver may number them differently.

Input

6 7
1 2
2 3
3 1
3 4
4 5
5 4
5 6

Output

3
3 3 3 2 2 1

The SCCs are {1,2,3}, {4,5} and {6}. Edges between them only go toward later groups in that list.

Practical applications

Use Tarjan for SCC condensation, cycle-region analysis and as a memory-saving alternative to Kosaraju. For a DAG, every SCC is a singleton. SCCs describe mutual reachability, not undirected connectivity, bridges or biconnected components. In 2-SAT compare complementary literal components, then derive assignment using the chosen extraction order.

Check your understanding

Which discovered neighbor may lower low[v]?

Put it into practice

Print all edges of the condensation graph and verify it is acyclic.