Tarjan: Difference between revisions
m
→{{header|11l}}: Void
m (→{{header|J}}: cleaner) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
(11 intermediate revisions by 3 users not shown) | |||
Line 13:
;References:
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].
See also: [[Kosaraju]]
<br><br>
Line 42 ⟶ 44:
.tarjan_algo()
F _visitor(this) ->
‘
Recursive function that finds SCC's
Line 628 ⟶ 630:
<syntaxhighlight lang=J>tarjan=: {{
coerase ([ cocurrent)
graph=: y NB. connection matrix of a directed graph
result=: stack=: i.index=: 0
Line 649 ⟶ 651:
end.
if. lolinks =&(y&{) indices do.
component=. loc }. stack
onstack=: 0 component} onstack
result=: result,<component
stack=:
end.
}}
Line 663 ⟶ 666:
}}</syntaxhighlight>
<syntaxhighlight lang=J>
}}</syntaxhighlight>▼
<syntaxhighlight lang=J> tarjan digraph1▼
┌─────┬───┬───┬─┐
│0 1 2│5 6│3 4│7│
└─────┴───┴───┴─┘</syntaxhighlight>
</syntaxhighlight>▼
=={{header|Java}}==
<syntaxhighlight lang="java">▼
▲<syntaxhighlight>
import java.util.ArrayList;
import java.util.HashMap;
Line 902 ⟶ 888:
Results in the zero-base scheme: Array{Int64,1}[[2, 1, 0], [6, 5], [4, 3], [7]]
</pre>
=={{header|K}}==
Implementation:
r::s::!i::0
t::+`o`j`k!(#g)#'0,2##g
L::{[g;v]
t[v]:1,i,i; s,:v; i+:1
{[g;v;w]
$[t[`k;w]=#g; L w; ~t[`o;w]; :0N]
t[`j;v]&:t[`j;w]}[g;v]'g v
$[=/t[`j`k;v]
[a:*&v=s; c:a_s; t[`o;c]:0; s::a#s; r,:,c]
]}[g]
{[g;v] $[t[`k;v]=#g; L v; ]}[g]'!#g
Example:
<syntaxhighlight lang=K>F (1;2;0;1 2 4;3 5;2 6;5;4 6 7)
(0 1 2
5 6
3 4
▲ ,7)</syntaxhighlight>
tested with ngn/k
=={{header|Kotlin}}==
Line 2,023 ⟶ 2,035:
{{libheader|Wren-seq}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="
import "./dynamic" for Tuple
class Node {
|