Recursive and iterative implementation on Kosaraju algorithm

Question

Kosaraju algorithm is mainly phrased as two recursive subroutines running postorder DFS twice to mark SCCs with linear time complexity O(V+E) below,

1. For each vertex \$u\$ of the graph, mark \$u\$ as unvisited. Let \$L\$ be empty.

2. For each vertex \$u\$ of the graph do Visit(\$u\$), where Visit(\$u\$) is the recursive subroutine:
   If \$u\$ is unvisited then:
   1. Mark \$u\$ as visited.
   2. For each out-neighbour \$v\$ of \$u\$, do Visit(\$v\$).
   3. Prepend \$u\$ to \$L\$.
   Otherwise do nothing.

3. For each element \$u\$ of \$L\$ in order, do Assign(\$u\$,\$u\$) where Assign(\$u\$,\$root\$) is the recursive subroutine:
   If \$u\$ has not been assigned to a component then:
   1. Assign \$u\$ as belonging to the component whose root is \$root\$.
   2. For each in-neighbour \$v\$ of \$u\$, do Assign(\$v\$,\$root\$).
   Otherwise do nothing.

Here is the recursive implementation in Python according to the above recipe,

def kosaraju(G):
 
 # postorder DFS on G to transpose the graph and push root vertices to L
 
 N = len(G)
 T, L, U = [[] for _ in range(N)], [], [False] * N
 
 def visit(u):
 if not U[u]:
 U[u] = True
 for v in G[u]:
 visit(v)
 T[v].append(u)
 L.append(u)
 
 for u in range(N):
 visit(u)
 
 # postorder DFS on T to pop root vertices from L and mark SCCs
 
 C = [None] * N
 
 def assign(u, r):
 if U[u]:
 U[u] = False
 C[u] = r
 for v in T[u]:
 assign(v, r)
 
 while L:
 u = L.pop()
 assign(u, u)
 
 return C

The following iterative implementation scales well against the stack overflow due to excessively deep recursion. I revised the inner loop of the first iterative DFS so the linear time complexity O(V+E) is guaranteed now, however it deserves to be shared for further improvement.
I'll be glad about all your opinions or alternative implementations.

def kosaraju(G):
 
 # postorder DFS on G to transpose the graph and push root vertices to L
 N = len(G)
 T, L, U = [[] for _ in range(N)], [], [False] * N
 for u in range(N):
 if not U[u]:
 U[u], S = True, [u]
 while S:
 u, done = S[-1], True
 for v in G[u]:
 T[v].append(u)
 if not U[v]:
 U[v], done = True, False
 S.append(v)
 break
 if done:
 S.pop()
 L.append(u)
 
 # postorder DFS on T to pop root vertices from L and mark SCCs
 C = [None] * N
 while L:
 r = L.pop()
 S = [r]
 if U[r]:
 U[r], C[r] = False, r
 while S:
 u, done = S[-1], True
 for v in T[u]:
 if U[v]:
 U[v] = done = False
 S.append(v)
 C[v] = r
 break
 if done:
 S.pop()
 
 return C

Test example:

G = [[1], [0, 2], [0, 3, 4], [4], [5], [6], [4], [6]]
print(kosaraju(G)) # => [0, 0, 0, 3, 4, 4, 4, 7]

enter image description here

Answer 1

(Work in progress)
I find the recursive variant pleasant enough to read:
• It picks up the names from the description referred
• The meaning of additional single-letter names isn't hard to guess
• there are comments to what's what

Main gripe: What can I use kosaraju(G) for, does it return something useful?
Have your source code document (non-private) parts:
Use docstrings.

Using loop-else, you don't need a done flag

def kosaraju(G):
 """ For a graph G given as a list of lists of node numbers
 find the strongly connected components.
 Use Kosaraju's algorithm:
 for each unvisited node, traverse and mark visited its out-neighbours,
 then add it to a sequence L
 for each unassigned node taken from L in reverse order,
 assign it to the same new SCC as all nodes reached via in-neighbours
 """
 # postorder DFT on G to transpose the graph and push root vertices to L
 N = len(G)
 T, L, visited = [[] for _ in range(N)], [], [False] * N
 for u in range(N):
 if visited[u]:
 continue
 visited[u], stack = True, [u]
 while stack:
 u = stack[-1]
 for v in G[u]:
 T[v].append(u)
 if not visited[v]:
 visited[v] = True
 stack.append(v)
 break
 else:
 stack.pop()
 L.append(u)
 # print("L:", L)
 # try and follow en.wikipedia's hint and have
 # visited indication share storage with the final assignment
 assigned = visited
 
 # postorder DFT on T to pop root vertices from L and mark SCCs
 assigned = visited # C = [None] * N
 while L:
 root = L.pop()
 if not visited[root] is True:
 continue
 assigned[root] = root
 stack = [root]
 while stack:
 # print("T[" + stack[-1] + "]: " + T[stack[-1]])
 for v in T[stack[-1]]:
 if visited[v] is True:
 stack.append(v)
 assigned[v] = root
 break
 else:
 stack.pop()
 
 return assigned
if __name__ == '__main__':
 G = [[], [5, 4], [3, 11, 6], [7], [2, 8, 10], [7, 5, 3],
 [8, 11], [9], [2, 8], [3], [1], [9, 6]] 
 print(kosaraju(G))