1. One-Liner
Tarjan finds strongly connected components in O(V+E) with one DFS using indices, lowlink, and a stack of the current DFS path.
2. The Problem It Solves
Decompose a directed graph into maximal subsets where every vertex can reach every other in the subset — used in 2-SAT, compiler analysis, dead-code detection.
3. The Core Idea
Track earliest reachable DFS index via tree/back edges (lowlink). When lowlink[u]==index[u], u is root of an SCC — pop stack until u.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | DFS; assign index[u], low[u]=index[u]; push u on stack |
| 2 | For edge u→v: if v unvisited recurse; low[u]=min(low[u], low[v]); if v on stack, low[u]=min(low[u], index[v]) |
| 3 | After neighbors: if low[u]==index[u], pop until u — one SCC |
5. Dry Run Example
Cycle 0→1→2→0: one SCC {0,1,2}. Add 3→0: 3 is its own SCC first, then the cycle component.
6. Key Properties
| Property | Value |
|---|---|
| One pass | Single DFS |
| vs Kosaraju | No transpose graph needed |
7. Where It Is Used
| Domain | Use |
|---|---|
| Compilers | Control-flow SCCs |
| Social graphs | Community cores |
8. Interview Tips
Explain lowlink; on-stack set vs Kosaraju’s two passes. Edge cases: self-loops, multi-edges.
9. Comparison with Other Algorithms
| Tarjan | Kosaraju | |
|---|---|---|
| Passes | 1 DFS | 2 DFS + transpose |
| Concept | Lowlink | Finish order |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
Implementation Example (PYTHON)
def tarjan_scc(n, adj):
index, low = [0]*n, [0]*n
stack, on = [], [False]*n
idx, sccs = [1], []
def strongconnect(v):
index[v] = low[v] = idx[0]; idx[0]+=1
stack.append(v); on[v]=True
for w in adj[v]:
if index[w]==0: strongconnect(w); low[v]=min(low[v],low[w])
elif on[w]: low[v]=min(low[v],index[w])
if low[v]==index[v]:
comp=[]
while True:
u=stack.pop(); on[u]=False; comp.append(u)
if u==v: break
sccs.append(comp)
for v in range(n):
if index[v]==0: strongconnect(v)
return sccs