Strongly Connected Components

kosaraju.py

def kosaraju(outList):
    n = len(outList) # n is 1 more than the number of vertices, for convenience
    visited = [False]*n
    components = [None]*n
    L = []

    def visit(u):
        if not visited[u]:
            visited[u] = True
            for v in inList[u]:
                visit(v)
            L.append(u)

    def assign(u, c):
        if not components[u]:
            components[u] = c
            for v in outList[u]:
                assign(v, c)

    #compute transpose graph
    inList = [[] for i in range(n)]
    for u in range(1, n):
        for v in outList[u]:
            inList[v].append(u)

    for u in range(1,n):
        if not visited[u]:
            visit(u)

    c = 0
    for u in reversed(L):
        if not components[u]:
            c += 1
            assign(u, c)

    return components

# outList = [[], [2], [3, 5, 6], [4, 7], [3, 8], [1, 6], [7], [6], [4, 7]]
# https://upload.wikimedia.org/wikipedia/commons/5/5c/Scc.png

tarjan.py

def tarjan(outList):
    n = len(outList) # n is 1 more than the number of vertices, for convenience
    S = []
    disc = [None] * n
    onStack = [False] * n
    lowLink = [None] * n
    components = [None] * n

    t = 1
    c = 0

    def strongConnect(v):
        nonlocal t, c, disc, lowLink, components, onStack, S
        disc[v] = t
        lowLink[v] = t
        t += 1
        S.append(v)
        onStack[v] = True
        for w in outList[v]:
            if not disc[w]:
                strongConnect(w)
                lowLink[v] = min(lowLink[v], lowLink[w])
            elif onStack[w]:
                lowLink[v] = min(lowLink[v], lowLink[w])

        if lowLink[v] == disc[v]:
            c += 1
            while True:
                w = S.pop()
                onStack[w] = False
                components[w] = c
                if w == v:
                    break

    for v in range(1,n):
        if not disc[v]:
            strongConnect(v)

    return components

# outList = [[], [2], [3, 5, 6], [4, 7], [3, 8], [1, 6], [7], [6], [4, 7]]
# https://upload.wikimedia.org/wikipedia/commons/5/5c/Scc.png