Strongly Connected Components

def countSCC(n, edges):
    out = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]
    for a, b in edges:
        out[a].append(b)
        rev[b].append(a)
    done = [False] * n
    # fwd[v] == s: the search forward from s reached v. bwd[v] == s: v reaches s.
    fwd = [-1] * n
    bwd = [-1] * n
    count = 0
    for s in range(n):
        if done[s]:
            continue
        count += 1
        # Every node s can reach.
        fwd[s] = s
        reached = [s]
        stack = [s]
        while stack:
            node = stack.pop()
            for nxt in out[node]:
                if fwd[nxt] != s:
                    fwd[nxt] = s
                    reached.append(nxt)
                    stack.append(nxt)
        # Every node that can reach s.
        bwd[s] = s
        stack = [s]
        while stack:
            node = stack.pop()
            for prev in rev[node]:
                if bwd[prev] != s:
                    bwd[prev] = s
                    stack.append(prev)
        # The nodes found both ways form the component of s.
        for v in reached:
            if bwd[v] == s:
                done[v] = True
    return count

def countSCC(n, edges):
    out = [[] for _ in range(n)]
    rev = [[] for _ in range(n)]
    for a, b in edges:
        out[a].append(b)
        rev[b].append(a)
    # Pass 1: depth first search on the graph, listing each node when it finishes.
    seen = [False] * n
    order = []
    for start in range(n):
        if seen[start]:
            continue
        seen[start] = True
        # Each frame is [node, next edge to try].
        stack = [[start, 0]]
        while stack:
            frame = stack[-1]
            node, i = frame
            if i < len(out[node]):
                frame[1] += 1
                nxt = out[node][i]
                if not seen[nxt]:
                    seen[nxt] = True
                    stack.append([nxt, 0])
            else:
                stack.pop()
                order.append(node)
    # Pass 2: on the reversed graph, start from the last node to finish.
    # Each search collects exactly one component.
    done = [False] * n
    count = 0
    for start in reversed(order):
        if done[start]:
            continue
        count += 1
        done[start] = True
        stack = [start]
        while stack:
            node = stack.pop()
            for prev in rev[node]:
                if not done[prev]:
                    done[prev] = True
                    stack.append(prev)
    return count

def countSCC(n, edges):
    out = [[] for _ in range(n)]
    for a, b in edges:
        out[a].append(b)
    index = [-1] * n      # discovery time, -1 while unvisited
    low = [0] * n         # earliest discovery time the node can reach and still return from
    on_stack = [False] * n
    stack = []            # visited nodes whose component is still open
    time = 0
    count = 0
    for start in range(n):
        if index[start] != -1:
            continue
        index[start] = low[start] = time
        time += 1
        stack.append(start)
        on_stack[start] = True
        # The depth first search keeps its own call stack: [node, next edge to try].
        calls = [[start, 0]]
        while calls:
            frame = calls[-1]
            node, i = frame
            if i < len(out[node]):
                frame[1] += 1
                nxt = out[node][i]
                if index[nxt] == -1:
                    index[nxt] = low[nxt] = time
                    time += 1
                    stack.append(nxt)
                    on_stack[nxt] = True
                    calls.append([nxt, 0])
                elif on_stack[nxt]:
                    # An edge back into an open component.
                    low[node] = min(low[node], index[nxt])
            else:
                calls.pop()
                if calls:
                    parent = calls[-1][0]
                    low[parent] = min(low[parent], low[node])
                # Nothing below node reaches above it: node closes a component.
                if low[node] == index[node]:
                    count += 1
                    while True:
                        w = stack.pop()
                        on_stack[w] = False
                        if w == node:
                            break
    return count