Tarjan's Algorithm

tarjan.py

def tarjan(tree):
    tree[0] = -1
    # record the search order, i.e., the timestep
    dfn = [-1] * len(tree)
    # record the the smallest timestep in a SCC
    low = [-1] * len(tree)
    # push the visited into the stack
    stack, onstack = [], [False] * len(tree)

    def connect(i, timestep):
        dfn[i] = low[i] = timestep[0]
        timestep[0] += 1
        stack.append(i)
        onstack[i] = True

        for j, head in enumerate(tree):
            if head != i:
                continue
            if dfn[j] == -1:
                yield from connect(j, timestep)
                low[i] = min(low[i], low[j])
            elif onstack[j]:
                low[i] = min(low[i], dfn[j])

        # a SCC is completed
        if low[i] == dfn[i]:
            cycle = [stack.pop()]
            while cycle[-1] != i:
                onstack[cycle[-1]] = False
                cycle.append(stack.pop())
            onstack[i] = False
            # ignore the self-loop
            if len(cycle) > 1:
                yield cycle

    timestep = [0]
    for i in range(len(tree)):
        if dfn[i] == -1:
            yield from connect(i, timestep)