Decompose directed graphs into SCCs using Kosaraju or Tarjan
Nodes mutually reachable form components; condense graph into DAG for further analysis.
Use on directed graphs for condensation, cycle grouping, or reachability compression.
Kosaraju's two-pass (reverse graph + postorder) or Tarjan's low-link DFS to label components; condense SCCs into a DAG for further DP/greedy.
# 2D Grid DP Template (Unique Paths)
def unique_paths(m, n):
dp=[[0]*n for _ in range(m)]
for r in range(m): dp[r][0]=1
for c in range(n): dp[0][c]=1
for r in range(1,m):
for c in range(1,n):
dp[r][c]=dp[r-1][c]+dp[r][c-1]
return dp[m-1][n-1]Two DFS runs with reverse graph
def kosaraju(n, adj):
order=[]; vis=[False]*n
def dfs1(u):
vis[u]=True
for v in adj[u]:
if not vis[v]: dfs1(v)
order.append(u)
for i in range(n):
if not vis[i]: dfs1(i)
# build reverse graph
radj=[[] for _ in range(n)]
for u in range(n):
for v in adj[u]: radj[v].append(u)
comp=[-1]*n; cid=0
def dfs2(u):
comp[u]=cid
for v in radj[u]:
if comp[v]==-1: dfs2(v)
for u in reversed(order):
if comp[u]==-1:
dfs2(u); cid+=1
return compLow-link values via DFS stack
def tarjan(n, adj):
idx=[-1]*n; low=[0]*n; on=[False]*n; st=[]; res=[]; t=0
def dfs(u):
nonlocal t
idx[u]=low[u]=t; t+=1; st.append(u); on[u]=True
for v in adj[u]:
if idx[v]==-1:
dfs(v); low[u]=min(low[u], low[v])
elif on[v]:
low[u]=min(low[u], idx[v])
if low[u]==idx[u]:
comp=[]
while True:
x=st.pop(); on[x]=False; comp.append(x)
if x==u: break
res.append(comp)
for i in range(n):
if idx[i]==-1: dfs(i)
return resLinear in graph size.
Graph + recursion/stack.