CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)


From Rosetta Code
Tarjan is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
This page uses content from Wikipedia. The original article was at Graph. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's Algorithm is named for its discoverer, Robert Tarjan.



using System;
using System.Collections.Generic;
class Node
public int LowLink { get; set; }
public int Index { get; set; }
public int N { get; }
public Node(int n)
N = n;
Index = -1;
LowLink = 0;
class Graph
public HashSet<Node> V { get; }
public Dictionary<Node, HashSet<Node>> Adj { get; }
/// <summary>
/// Tarjan's strongly connected components algorithm
/// </summary>
public void Tarjan()
var index = 0; // number of nodes
var S = new Stack<Node>();
Action<Node> StrongConnect = null;
StrongConnect = (v) =>
// Set the depth index for v to the smallest unused index
v.Index = index;
v.LowLink = index;
// Consider successors of v
foreach (var w in Adj[v])
if (w.Index < 0)
// Successor w has not yet been visited; recurse on it
v.LowLink = Math.Min(v.LowLink, w.LowLink);
else if (S.Contains(w))
// Successor w is in stack S and hence in the current SCC
v.LowLink = Math.Min(v.LowLink, w.Index);
// If v is a root node, pop the stack and generate an SCC
if (v.LowLink == v.Index)
Console.Write("SCC: ");
Node w;
w = S.Pop();
Console.Write(w.N + " ");
} while (w != v);
foreach (var v in V)
if (v.Index < 0)


class Tarjan{
// input: graph G = (V, Es)
// output: set of strongly connected components (sets of vertices)
// Ick: class holds global state for strongConnect(), otherwise inert
const INDEX=0, LOW_LINK=1, ON_STACK=2;
fcn init(graph){
var index=0, stack=List(), components=List(),
// convert graph to ( (index,lowlink,onStack),(id,links)), ...)
// sorted by id
foreach v in (graph){ G[v[0]]=T( L(Void,Void,False),v) }
foreach v in (G){ if(v[0][INDEX]==Void) strongConnect(v) }
println("List of strongly connected components:");
foreach c in (components){ println(c.reverse().concat(",")) }
returnClass(components); // over-ride return of class instance
fcn strongConnect(v){ // v is ( (index,lowlink,onStack), (id,links) )
// Set the depth index for v to the smallest unused index
v0:=v[0]; v0[INDEX]=v0[LOW_LINK]=index;
// Consider successors of v
foreach idx in (v[1][1,*]){ // links of v to other vs
w,w0 := G[idx],w[0]; // well, that is pretty vile
strongConnect(w); // Successor w not yet visited; recurse on it
else if(w0[ON_STACK])
// Successor w is in stack S and hence in the current SCC
// If v is a root node, pop the stack and generate an SCC
strong:=List(); // start a new strongly connected component
w,w0 := stack.pop(), w[0];
strong.append(w[1][0]); // add w to strongly connected component
components.append(strong); // output strongly connected component
   // graph from
// with vertices id zero based (vs 1 based in article)
// ids start at zero and are consecutive (no holes), graph is unsorted
graph:= // ( (id, links/Edges), ...)
T( T(0,1), T(2,0), T(5,2,6), T(6,5),
T(1,2), T(3,1,2,4), T(4,5,3), T(7,4,7,6) );