View source for Talk:Tarjan

===Correctness?===
The pseudo code from Wikipedia does not seem correct.  I ran into problems when trying to translate it into Python.  To corroborate, I tested the Perl code on the task page, with a simple graph where there are only two nodes with one directed edge between them:
<lang perl>my %test1 = (
  0 => [1],
);
 
print "Strongly connected components:\n";
print join(', ', sort @$_) . "\n" for tarjan(%test1);</lang>
which outputs
<pre>Strongly connected components:
1
0</pre>

Any thoughts? --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 08:37, 9 March 2020 (UTC)

    Perhaps the task description needs better detail. The code examples work if all points are those of a digraph so 0 => 1 means that 0 is 
    connected to 1 the same way as 1 is to 0. Note that the examples never show reciprocal connections -- if there is a 2 => 4,  we never 
    see 4 => 2 listed in the data --  it's a digraph.
    --[[User:Wherrera|Wherrera]] ([[User talk:Wherrera|talk]]) 08:19, 9 March 2020 (UTC)

That can't be right. "Strongly connected" means between two nodes A and B, there is a path from A to B *and* there is a path from B to A, which only makes sense if edges are directed. If all connections are bidirectional, there is no difference between "connected" and "strongly connected", and the algorithm only needs a depth-first traversal without much of the bookkeeping at all. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 08:37, 9 March 2020 (UTC)