Kosaraju: Difference between revisions
Insert a working python3 version of the python code
m (→{{header|Pascal}}: cosmetic) |
Lambda-calc (talk | contribs) (Insert a working python3 version of the python code) |
||
Line 1,216:
{1,1,1,4,4,6,6,8}
</pre>
=={{header|Python3}}==
<syntaxhighlight lang="python3">def kosaraju(g):
size = len(g)
vis = [False] * size
l = [0] * size
x = size
t = [[] for _ in range(size)]
def visit(u):
nonlocal x
if not vis[u]:
vis[u] = True
for v in g[u]:
visit(v)
t[v].append(u)
x -= 1
l[x] = u
for u in range(size):
visit(u)
c = [0] * size
def assign(u, root):
if vis[u]:
vis[u] = False
c[u] = root
for v in t[u]:
assign(v, root)
for u in l:
assign(u, u)
return c
g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
print(kosaraju(g))</syntaxhighlight>
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Python}}==
| |||