Kosaraju: Difference between revisions
→{{header|Perl 6}}: Add a Perl 6 example
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl 6 example) |
|||
Line 340:
[7]
</pre>
=={{header|Perl 6}}==
{{works with|Rakudo|2018.09}}
{{trans|Python}}{{trans|Kotlin}}
<lang perl6>sub kosaraju (*@g) {
my %visited;
my @stack;
my @transpose;
my @connected;
sub visit ($u) {
unless %visited{$u} {
%visited{$u} = True;
for |@g[$u] -> $v {
visit($v);
@transpose[$v].push: $u;
}
@stack.unshift: $u;
}
}
sub assign ($u, $root) {
if %visited{$u} {
%visited{$u} = False;
@connected[$u] = $root;
assign($_, $root) for |@transpose[$u];
}
}
.&visit for ^@g;
assign($_, $_) for @stack;
@connected
}
my @verticies = (1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7);
my @connected = kosaraju @verticies;
my %scc;
@connected.antipairs.map: { %scc{$_.key}.push: $_.value }
say ' Connected graph: ', @connected;
say 'Strongly connected components: ', |%scc.sort».values».Slip</lang>
{{out}}
<pre> Connected graph: [0 0 0 3 3 5 5 7]
Strongly connected components: [0 1 2][3 4][5 6][7]</pre>
=={{header|Python}}==
| |||