Tarjan: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|J}}) |
m (→{{header|Wren}}: Minor tidy) |
||
| (11 intermediate revisions by 2 users not shown) | |||
Line 13:
;References:
* The article on [[wp:Tarjan's_strongly_connected_components_algorithm|Wikipedia]].
See also: [[Kosaraju]]
<br><br>
Line 628 ⟶ 630:
<syntaxhighlight lang=J>tarjan=: {{
coerase ([ cocurrent) cocreate'' NB. following =: declarations are temporary, expiring when we finish
graph=: y NB. connection matrix of a directed graph
result=: stack=: i.index=: 0
Line 650 ⟶ 651:
end.
if. lolinks =&(y&{) indices do.
component=. loc }. stack
onstack=: 0 component} onstack
result=: result,<component
stack=:
end.
}}
Line 664 ⟶ 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 903 ⟶ 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,024 ⟶ 2,035:
{{libheader|Wren-seq}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="
import "./dynamic" for Tuple
class Node {
| |||