ZERO / HERO
Neighbourhoods you can circle

Strongly Connected Components

The analogy

On a map of one-way streets, some clusters let you drive from anywhere to anywhere and back. Others you can enter but never leave. Finding those mutually-reachable clusters lets you shrink the whole messy map into a clean flowchart with no loops at all.

Visualizer

Finding the loops

step 1 / 7
ABCDEFG

A directed graph. Arrows are one-way streets, so reachability is no longer symmetric.V = 7, directed

def kosaraju(n, g, rg):
    seen, order = set(), []

    def dfs1(u):
        seen.add(u)
        for v in g[u]:
            if v not in seen:
                dfs1(v)
        order.append(u)              # finishing order

    for u in range(n):
        if u not in seen:
            dfs1(u)

    comp, sccs = {}, []
    def dfs2(u, cid):
        comp[u] = cid
        sccs[cid].append(u)
        for v in rg[u]:              # REVERSED graph
            if v not in comp:
                dfs2(v, cid)

    for u in reversed(order):
        if u not in comp:
            sccs.append([])
            dfs2(u, len(sccs) - 1)
    return sccs      # contract these -> always a DAG
Check yourself

You contract every SCC into a single node. What are you guaranteed?