Tarjan's Algorithm

Problem

Find all SCCs — maximal sets where every vertex can reach every other vertex.

Example:

0→1→2→0  (SCC: {0,1,2})
2→3      (SCC: {3})

disc[u] = discovery time
low[u]  = lowest disc reachable from subtree of u
on_stack[u] = is u currently on stack?

When low[u] == disc[u]: u is root of an SCC
  → pop stack until u popped = one SCC

Solutions

Python

def tarjan_scc(n, adj):
    disc = [-1]*n
    low = [0]*n
    on_stack = [False]*n
    stack = []
    timer = [0]
    sccs = []

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            scc = []
            while True:
                v = stack.pop()
                on_stack[v] = False
                scc.append(v)
                if v == u: break
            sccs.append(scc)

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return sccs

JavaScript

function tarjanSCC(n, adj) {
    const disc=new Array(n).fill(-1), low=new Array(n).fill(0);
    const onStack=new Array(n).fill(false), stack=[], sccs=[];
    let timer=0;
    const dfs=(u)=>{
        disc[u]=low[u]=timer++; stack.push(u); onStack[u]=true;
        for(const v of adj[u]){
            if(disc[v]===-1){dfs(v);low[u]=Math.min(low[u],low[v]);}
            else if(onStack[v])low[u]=Math.min(low[u],disc[v]);
        }
        if(low[u]===disc[u]){
            const scc=[];
            while(true){const v=stack.pop();onStack[v]=false;scc.push(v);if(v===u)break;}
            sccs.push(scc);
        }
    };
    for(let i=0;i<n;i++)if(disc[i]===-1)dfs(i);
    return sccs;
}

Java

import java.util.*;
int[] disc,low; boolean[] onStack; Deque<Integer> stack; int timer=0; List<List<Integer>> sccs=new ArrayList<>();
public List<List<Integer>> tarjan(int n, List<Integer>[] adj){
    disc=new int[n]; low=new int[n]; onStack=new boolean[n]; stack=new ArrayDeque<>();
    Arrays.fill(disc,-1);
    for(int i=0;i<n;i++) if(disc[i]==-1) dfs(i,adj);
    return sccs;
}
void dfs(int u,List<Integer>[]adj){
    disc[u]=low[u]=timer++; stack.push(u); onStack[u]=true;
    for(int v:adj[u]){
        if(disc[v]==-1){dfs(v,adj);low[u]=Math.min(low[u],low[v]);}
        else if(onStack[v])low[u]=Math.min(low[u],disc[v]);
    }
    if(low[u]==disc[u]){
        List<Integer> scc=new ArrayList<>();
        while(true){int v=stack.pop();onStack[v]=false;scc.add(v);if(v==u)break;}
        sccs.add(scc);
    }
}

C++

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int disc[100001],low[100001],timer_=0; bool onStk[100001];
stack<int> stk; vector<vector<int>> sccs;
void dfs(int u,vector<int>adj[]){
    disc[u]=low[u]=timer_++; stk.push(u); onStk[u]=true;
    for(int v:adj[u]){
        if(disc[v]==-1){dfs(v,adj);low[u]=min(low[u],low[v]);}
        else if(onStk[v])low[u]=min(low[u],disc[v]);
    }
    if(low[u]==disc[u]){
        vector<int> scc;
        while(true){int v=stk.top();stk.pop();onStk[v]=false;scc.push_back(v);if(v==u)break;}
        sccs.push_back(scc);
    }
}

C

/* C: same iterative version using explicit stack to avoid recursion depth issues */