Kosaraju: Difference between revisions
m
Combine Python entries with appropriate works with verbiage
Lambda-calc (talk | contribs) (Insert a working python3 version of the python code) |
Thundergnat (talk | contribs) m (Combine Python entries with appropriate works with verbiage) |
||
Line 1,217:
</pre>
=={{header|
Works with Python 2
<syntaxhighlight lang="python3">def kosaraju(g):▼
<syntaxhighlight lang="python">def kosaraju(g):▼
class nonlocal: pass▼
# 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.▼
size = len(g)
vis = [False] * size▼
t = [[]]*size # transpose graph▼
def visit(u):
nonlocal x▼
if not vis[u]:
vis[u] = True
for v in g[u]:
visit(v)
t[v]
nonlocal.x
l[nonlocal.x] = u
# 2. For each vertex u of the graph do visit(u)▼
for u in range(size):▼
for u in range(len(g)):▼
visit(u)
c = [0]
def assign(u, root):
Line 1,246 ⟶ 1,251:
assign(v, root)
# 3: For each element u of l in order, do assign(u, u)▼
for u in l:
assign(u, u)
Line 1,251 ⟶ 1,257:
return c
g = [[1], [2], [0], [1,2,4], [3,5], [2,6], [5], [4,6,7]]▼
print kosaraju(g)</syntaxhighlight>▼
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>
Syntax requirements have changed. This version works with Python 3.
▲<syntaxhighlight lang="python3">def kosaraju(g):
▲<syntaxhighlight lang="python">def kosaraju(g):
▲ class nonlocal: pass
▲ # 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
size = len(g)
▲ vis = [False] * size
▲ t = [[]]*size # transpose graph
def visit(u):
▲ nonlocal x
if not vis[u]:
vis[u] = True
for v in g[u]:
visit(v)
t[v]
l[
▲ for u in range(size):
▲ # 2. For each vertex u of the graph do visit(u)
▲ for u in range(len(g)):
visit(u)
c = [0] * size
def assign(u, root):
Line 1,293 ⟶ 1,291:
assign(v, root)
▲ # 3: For each element u of l in order, do assign(u, u)
for u in l:
assign(u, u)
Line 1,299 ⟶ 1,296:
return c
▲g = [[1], [2], [0], [1,2,4], [3,5], [2,6], [5], [4,6,7]]
▲g = [[1], [2], [0], [1, 2, 4], [3, 5], [2, 6], [5], [4, 6, 7]]
▲print kosaraju(g)</syntaxhighlight>
▲print(kosaraju(g))</syntaxhighlight>
{{out}}
<pre>[0, 0, 0, 3, 3, 5, 5, 7]</pre>
=={{header|Racket}}==
| |||