Strongly connected components

In a directed graph, a strongly connected component contains vertices that can all reach one another. Kosaraju uses two DFS passes.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Record vertices after finishing DFS in the original graph.
2. Reverse every edge.
3. Visit vertices in reverse finishing order in the reversed graph.
4. Each new traversal forms one SCC. Contracting SCCs creates a DAG.
5. The first DFS records finishing order. Reversing that order and traversing reversed edges isolates one SCC per second-pass search.

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

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>g(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
    }
    vector<vector<int>>rev(n+1);
    for(int v=1;v<=n;++v){
        for(int u:g[v]){
            rev[u].push_back(v);
        }
    }
    vector<bool>seen(n+1);
    vector<int>order,comp(n+1,-1);
    function<void(int)>first=[&](int v){
        seen[v]=true;
        for(int u:g[v]){
            if(!seen[u]){
                first(u);
            }
        }
        order.push_back(v); // Finishing order.
    };
    function<void(int,int)>second=[&](int v,int id){
        comp[v]=id;
        for(int u:rev[v]){
            if(comp[u]==-1){
                second(u,id);
            }
        }
    };
    for(int v=1;v<=n;++v){
        if(!seen[v]){
            first(v);
        }
    }
    reverse(order.begin(),order.end());
    int count=0;
    for(int v:order){
        if(comp[v]==-1){
            second(v,count++);
        }
    }
    cout<<count<<'\n';
    for(int vertex=1;vertex<=n;vertex++){
        if(vertex>1){
            cout<<' ';
        }
        cout<<comp[vertex]+1;
    }
    cout<<'\n';
}

Complexity analysis

O(V + E) time and space.

Example input and output

Read n m and m directed edges. Require 1≤n≤2000 for recursive DFS. Print the SCC count and one component label per vertex. Equal labels mean mutual reachability; component numbering is implementation-dependent.

Input

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

Output

3
1 1 2 2 3

The mutually reachable groups are {1,2}, {3,4}, and {5}. The edges between these groups point forward.

Practical applications

Use SCCs to compress a directed graph into a DAG, reason about cycles, and build 2-SAT algorithms.

Check your understanding

What graph do SCCs form after contraction?

Put it into practice

Group web pages by mutual reachability.