Kosaraju: Difference between revisions
m
→{{header|11l}}: Void
m (→{{header|K}}) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (4 intermediate revisions by 2 users not shown) | |||
Line 30:
V t = [[Int]()] * size
F visit(Int u) ->
I !@vis[u]
@vis[u] = 1B
Line 43:
V c = [0] * size
F assign(Int u, root) ->
I @vis[u]
@vis[u] = 0B
Line 769:
=={{header|K}}==
{{works with|ngn/k}}
<syntaxhighlight lang=K>F:{[g] / graph
n: #g / number of vertices
Line 780 ⟶ 781:
A'/2#,L / Assign
.=c}</syntaxhighlight>
<syntaxhighlight lang=K> F(1;2;0;1 2 4;3 5;2 6;5;4 6 7)
(0 1 2
3 4
5 6
,7)</syntaxhighlight>
Alternative implementation, without global assignments:
<syntaxhighlight lang=K>F:{[g] /graph
n:#g /number of vertices
G:@[n#,!0;g;,;!n] /transposed graph
V:{[g;L;x]$[^L?x;(1_(x,L)o[g]/g x),x;L]}[g]
L:|V/[!0;!#g] /Visit
A:{[G;c;u;r]$[0>c u;o[G]/[@[c;u;:;r];G u;r];c]}[G]
.=A/[n#-1;L;L]} /Assign</syntaxhighlight>
(result is the same)
{{works with|Kona}}<syntaxhighlight lang=K>F:{[g] / graph
n: #g / number of vertices
v::&n / visited?
L::!0 / dfs order
V: {[g;x] :[v x;;[v[x]:1;_f[g]'g x;L::x,L]];}[g]
V'!n / Visit
G: @[n#,!0;g;,;!n] / transposed graph
c::n#-1 / assigned components
A: {[G;x;y] :[-1=c x;[c[x]:y;G[x]_f[G]'y];]}[G]'
A'/2#,L / Assign
.=c}</syntaxhighlight>
(result is the same)
=={{header|Kotlin}}==
Line 1,706 ⟶ 1,733:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var gc = g.count
// 1. For each vertex u of the graph, mark u as unvisited. Let l be empty.
| |||