Strongly Connected Components

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 comp

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 res