Tarjan

Tarjan
You are encouraged to solve this task according to the task description, using any language you may know.

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.

References

• The article on Wikipedia.

See also: Kosaraju

11l

Translation of: Python: As class

T Graph
   String name
   [Char = [Char]] graph
   Int _order
   [Char = Int] disc
   [Char = Int] low
   [Char] stack
   [[Char]] scc

   F (name, connections)
      .name = name

      DefaultDict[Char, [Char]] g
      L(n) connections
         V (n1, n2) = (n[0], n[1])
         I n1 != n2
            g[n1].append(n2)
         E
            g[n1]
         g[n2]

      .graph = Dict(move(g))
      .tarjan_algo()

   F _visitor(this) -> N
      ‘
        Recursive function that finds SCC's
        using DFS traversal of vertices.

        Arguments:
            this        --> Vertex to be visited in this call.
            disc{}      --> Discovery order of visited vertices.
            low{}       --> Connected vertex of earliest discovery order
            stack       --> Ancestor node stack during DFS.
      ’
      .disc[this] = .low[this] = ._order
      ._order++
      .stack.append(this)

      L(neighbr) .graph[this]
         I neighbr !C .disc
            ._visitor(neighbr)
            .low[this] = min(.low[this], .low[neighbr])

         E I neighbr C .stack
            .low[this] = min(.low[this], .disc[neighbr])

      I .low[this] == .disc[this]
         [Char] new
         L
            V top = .stack.pop()
            new.append(top)
            I top == this
               L.break
         .scc.append(new)

   F tarjan_algo()
      ‘
        Recursive function that finds strongly connected components
        using the Tarjan Algorithm and function _visitor() to visit nodes.
      ’
      ._order = 0

      L(vertex) sorted(.graph.keys())
         I vertex !C .disc
            ._visitor(vertex)

L(n, m) [(‘Tx1’, ‘10 02 21 03 34’.split(‘ ’)),
         (‘Tx2’, ‘01 12 23’.split(‘ ’)),
         (‘Tx3’, ‘01 12 20 13 14 16 35 45’.split(‘ ’)),
         (‘Tx4’, ‘01 03 12 14 20 26 32 45 46 56 57 58 59 64 79 89 98 AA’.split(‘ ’)),
         (‘Tx5’, ‘01 12 23 24 30 42’.split(‘ ’))
         ]
   print("\n\nGraph('#.', #.):\n".format(n, m))
   V g = Graph(n, m)
   print(‘               :  ’sorted(g.disc.keys()).map(v -> String(v)).join(‘  ’))
   print(‘    DISC of ’(g.name‘:’)‘ ’sorted(g.disc.items()).map((_, v) -> v))
   print(‘     LOW of ’(g.name‘:’)‘ ’sorted(g.low.items()).map((_, v) -> v))
   V scc = (I !g.scc.empty {String(g.scc).replace(‘'’, ‘’).replace(‘,’, ‘’)[1 .< (len)-1]} E ‘’)
   print("\n   SCC's of "(g.name‘:’)‘ ’scc)

Output:

Graph('Tx1', [10, 02, 21, 03, 34]):

               :  0  1  2  3  4
    DISC of Tx1: [0, 2, 1, 3, 4]
     LOW of Tx1: [0, 0, 0, 3, 4]

   SCC's of Tx1: [4] [3] [1 2 0]


Graph('Tx2', [01, 12, 23]):

               :  0  1  2  3
    DISC of Tx2: [0, 1, 2, 3]
     LOW of Tx2: [0, 1, 2, 3]

   SCC's of Tx2: [3] [2] [1] [0]


Graph('Tx3', [01, 12, 20, 13, 14, 16, 35, 45]):

               :  0  1  2  3  4  5  6
    DISC of Tx3: [0, 1, 2, 3, 5, 4, 6]
     LOW of Tx3: [0, 0, 0, 3, 5, 4, 6]

   SCC's of Tx3: [5] [3] [4] [6] [2 1 0]


Graph('Tx4', [01, 03, 12, 14, 20, 26, 32, 45, 46, 56, 57, 58, 59, 64, 79, 89, 98, AA]):

               :  0  1  2  3  4  5  6  7  8  9  A
    DISC of Tx4: [0, 1, 2, 9, 4, 5, 3, 6, 8, 7, 10]
     LOW of Tx4: [0, 0, 0, 2, 3, 3, 3, 6, 7, 7, 10]

   SCC's of Tx4: [8 9] [7] [5 4 6] [3 2 1 0] [A]


Graph('Tx5', [01, 12, 23, 24, 30, 42]):

               :  0  1  2  3  4
    DISC of Tx5: [0, 1, 2, 3, 4]
     LOW of Tx5: [0, 0, 0, 0, 2]

   SCC's of Tx5: [4 3 2 1 0]

C

#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>

#ifndef min
#define min(x, y) ((x)<(y) ? (x) : (y))
#endif

struct edge {
	void *from;
	void *to;
};

struct components {
	int nnodes;
	void **nodes;
	struct components *next;
};

struct node {
	int index;
	int lowlink;
	bool onStack;
	void *data;
};

struct tjstate {
	int index;
	int sp;
	int nedges;
	struct edge *edges;
	struct node **stack;
	struct components *head;
	struct components *tail;
};

static int nodecmp(const void *l, const void *r)
{
	return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
}

static int strongconnect(struct node *v, struct tjstate *tj)
{
	struct node *w;

	/* Set the depth index for v to the smallest unused index */
	v->index = tj->index;
	v->lowlink = tj->index;
	tj->index++;
	tj->stack[tj->sp] = v;
	tj->sp++;
	v->onStack = true;

	for (int i = 0; i<tj->nedges; i++) {
		/* Only consider nodes reachable from v */
		if (tj->edges[i].from != v) {
			continue;
		}
		w = tj->edges[i].to;
		/* Successor w has not yet been visited; recurse on it */
		if (w->index == -1) {
			int r = strongconnect(w, tj);
			if (r != 0)
				return r;
			v->lowlink = min(v->lowlink, w->lowlink);
		/* Successor w is in stack S and hence in the current SCC */
		} else if (w->onStack) {
			v->lowlink = min(v->lowlink, w->index);
		}
	}

	/* If v is a root node, pop the stack and generate an SCC */
	if (v->lowlink == v->index) {
		struct components *ng = malloc(sizeof(struct components));
		if (ng == NULL) {
			return 2;
		}
		if (tj->tail == NULL) {
			tj->head = ng;
		} else {
			tj->tail->next = ng;
		}
		tj->tail = ng;
		ng->next = NULL;
		ng->nnodes = 0;
		do {
			tj->sp--;
			w = tj->stack[tj->sp];
			w->onStack = false;
			ng->nnodes++;
		} while (w != v);
		ng->nodes = malloc(ng->nnodes*sizeof(void *));
		if (ng == NULL) {
			return 2;
		}
		for (int i = 0; i<ng->nnodes; i++) {
			ng->nodes[i] = tj->stack[tj->sp+i]->data;
		}
	}
	return 0;
}

static int ptrcmp(const void *l, const void *r)
{
	return (ptrdiff_t)((struct node *)l)->data
		- (ptrdiff_t)((struct node *)r)->data;
}

/**
 * Calculate the strongly connected components using Tarjan's algorithm:
 * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 *
 * Returns NULL when there are invalid edges and sets the error to:
 * 1 if there was a malformed edge
 * 2 if malloc failed
 *
 * @param number of nodes
 * @param data of the nodes (assumed to be unique)
 * @param number of edges
 * @param data of edges
 * @param pointer to error code
 */
struct components *tarjans(
		int nnodes, void *nodedata[],
		int nedges, struct edge *edgedata[],
		int *error)
{
	struct node nodes[nnodes];
	struct edge edges[nedges];
	struct node *stack[nnodes];
	struct node *from, *to;
	struct tjstate tj = {0, 0, nedges, edges, stack, NULL, .tail=NULL};

	// Populate the nodes
	for (int i = 0; i<nnodes; i++) {
		nodes[i] = (struct node){-1, -1, false, nodedata[i]};
	}
	qsort(nodes, nnodes, sizeof(struct node), ptrcmp);

	// Populate the edges
	for (int i = 0; i<nedges; i++) {
		from = bsearch(edgedata[i]->from, nodes, nnodes,
			sizeof(struct node), nodecmp);
		if (from == NULL) {
			*error = 1;
			return NULL;
		}
		to = bsearch(edgedata[i]->to, nodes, nnodes,
			sizeof(struct node), nodecmp);
		if (to == NULL) {
			*error = 1;
			return NULL;
		}
		edges[i] = (struct edge){.from=from, .to=to};
	}

	//Tarjan's
	for (int i = 0; i < nnodes; i++) {
		if (nodes[i].index == -1) {
			*error = strongconnect(&nodes[i], &tj);
			if (*error != 0)
				return NULL;
		}
	}
	return tj.head;
}

C#

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;

            index++;
            S.Push(v);

            // Consider successors of v
            foreach (var w in Adj[v])
                if (w.Index < 0)
                {
                    // Successor w has not yet been visited; recurse on it
                    StrongConnect(w);
                    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;
                do
                {
                    w = S.Pop();
                    Console.Write(w.N + " ");
                } while (w != v);

                Console.WriteLine();
            }
        };

        foreach (var v in V)
            if (v.Index < 0)
                StrongConnect(v);
    }
}

C++

//
// C++ implementation of Tarjan's strongly connected components algorithm
// See https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
//
#include <algorithm>
#include <iostream>
#include <list>
#include <string>
#include <vector>

struct noncopyable {
    noncopyable() {}
    noncopyable(const noncopyable&) = delete;
    noncopyable& operator=(const noncopyable&) = delete;
};

template <typename T>
class tarjan;

template <typename T>
class vertex : private noncopyable {
public:
    explicit vertex(const T& t) : data_(t) {}
    void add_neighbour(vertex* v) {
        neighbours_.push_back(v);
    }
    void add_neighbours(const std::initializer_list<vertex*>& vs) {
        neighbours_.insert(neighbours_.end(), vs);
    }
    const T& get_data() {
        return data_;
    }
private:
    friend tarjan<T>;
    T data_;
    int index_ = -1;
    int lowlink_ = -1;
    bool on_stack_ = false;
    std::vector<vertex*> neighbours_;
};

template <typename T>
class graph : private noncopyable {
public:
    vertex<T>* add_vertex(const T& t) {
        vertexes_.emplace_back(t);
        return &vertexes_.back();
    }
private:
    friend tarjan<T>;
    std::list<vertex<T>> vertexes_;
};

template <typename T>
class tarjan  : private noncopyable {
public:
    using component = std::vector<vertex<T>*>;
    std::list<component> run(graph<T>& graph) {
        index_ = 0;
        stack_.clear();
        strongly_connected_.clear();
        for (auto& v : graph.vertexes_) {
            if (v.index_ == -1)
                strongconnect(&v);
        }
        return strongly_connected_;
    }
private:
    void strongconnect(vertex<T>* v) {
        v->index_ = index_;
        v->lowlink_ = index_;
        ++index_;
        stack_.push_back(v);
        v->on_stack_ = true;
        for (auto w : v->neighbours_) {
            if (w->index_ == -1) {
                strongconnect(w);
                v->lowlink_ = std::min(v->lowlink_, w->lowlink_);
            }
            else if (w->on_stack_) {
                v->lowlink_ = std::min(v->lowlink_, w->index_);
            }
        }
        if (v->lowlink_ == v->index_) {
            strongly_connected_.push_back(component());
            component& c = strongly_connected_.back();
            for (;;) {
                auto w = stack_.back();
                stack_.pop_back();
                w->on_stack_ = false;
                c.push_back(w);
                if (w == v)
                    break;
            }
        }
    }
    int index_ = 0;
    std::list<vertex<T>*> stack_;
    std::list<component> strongly_connected_;
};

template <typename T>
void print_vector(const std::vector<vertex<T>*>& vec) {
    if (!vec.empty()) {
        auto i = vec.begin();
        std::cout << (*i)->get_data();
        for (++i; i != vec.end(); ++i)
            std::cout << ' ' << (*i)->get_data();
    }
    std::cout << '\n';
}

int main() {
    graph<std::string> g;
    auto andy = g.add_vertex("Andy");
    auto bart = g.add_vertex("Bart");
    auto carl = g.add_vertex("Carl");
    auto dave = g.add_vertex("Dave");
    auto earl = g.add_vertex("Earl");
    auto fred = g.add_vertex("Fred");
    auto gary = g.add_vertex("Gary");
    auto hank = g.add_vertex("Hank");

    andy->add_neighbour(bart);
    bart->add_neighbour(carl);
    carl->add_neighbour(andy);
    dave->add_neighbours({bart, carl, earl});
    earl->add_neighbours({dave, fred});
    fred->add_neighbours({carl, gary});
    gary->add_neighbour(fred);
    hank->add_neighbours({earl, gary, hank});

    tarjan<std::string> t;
    for (auto&& s : t.run(g))
        print_vector(s);
    return 0;
}

Output:

Carl Bart Andy
Gary Fred
Earl Dave
Hank

Go

package main

import (
    "fmt"
    "math/big"
)

// (same data as zkl example)
var g = [][]int{
    0: {1},
    2: {0},
    5: {2, 6},
    6: {5},
    1: {2},
    3: {1, 2, 4},
    4: {5, 3},
    7: {4, 7, 6},
}

func main() {
    tarjan(g, func(c []int) { fmt.Println(c) })
}

// the function calls the emit argument for each component identified.
// each component is a list of nodes.
func tarjan(g [][]int, emit func([]int)) {
    var indexed, stacked big.Int
    index := make([]int, len(g))
    lowlink := make([]int, len(g))
    x := 0
    var S []int
    var sc func(int) bool
    sc = func(n int) bool {
        index[n] = x
        indexed.SetBit(&indexed, n, 1)
        lowlink[n] = x
        x++
        S = append(S, n)
        stacked.SetBit(&stacked, n, 1)
        for _, nb := range g[n] {
            if indexed.Bit(nb) == 0 {
                if !sc(nb) {
                    return false
                }
                if lowlink[nb] < lowlink[n] {
                    lowlink[n] = lowlink[nb]
                }
            } else if stacked.Bit(nb) == 1 {
                if index[nb] < lowlink[n] {
                    lowlink[n] = index[nb]
                }
            }
        }
        if lowlink[n] == index[n] {
            var c []int
            for {
                last := len(S) - 1
                w := S[last]
                S = S[:last]
                stacked.SetBit(&stacked, w, 0)
                c = append(c, w)
                if w == n {
                    emit(c)
                    break
                }
            }
        }
        return true
    }
    for n := range g {
        if indexed.Bit(n) == 0 && !sc(n) {
            return
        }
    }
}

Output:

[2 1 0]
[6 5]
[4 3]
[7]

J

Brute force implementation from wikipedia pseudocode:

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
  undef=: #graph
  lolinks=: indices=: undef"_1 graph
  onstack=: 0"_1 graph
  strongconnect=: {{
    indices=: index y} indices
    lolinks=: index y} lolinks
    onstack=:     1 y} onstack
    stack=: stack,y
    index=: index+1
    for_w. y{::graph do.
      if. undef = w{indices do.
        strongconnect w
        lolinks=: (<./lolinks{~y,w) y} lolinks
      elseif. w{onstack do.
        lolinks=: (<./lolinks{~y,w) y} lolinks
      end.
    end.
    if. lolinks =&(y&{) indices do.
      loc=. stack i. y
      component=. loc }. stack
      onstack=: 0 component} onstack
      result=: result,<component
      stack=: loc {. stack
    end.
  }}
  for_Y. i.#graph do.
    if. undef=Y{indices do.
      strongconnect Y
    end.
  end.
  result
}}

Example use, with graph from wikipedia animated example:

   tarjan 1;2;0;1 2 4;3 5;2 6;5;4 6 7
┌─────┬───┬───┬─┐
│0 1 2│5 6│3 4│7│
└─────┴───┴───┴─┘

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public final class TarjanSCC {
	
	public static void main(String[] aArgs) {
		Graph graph = new Graph(8);
		
		graph.addDirectedEdge(0, 1);
		graph.addDirectedEdge(1, 2); graph.addDirectedEdge(1, 7);
		graph.addDirectedEdge(2, 3); graph.addDirectedEdge(2, 6);
		graph.addDirectedEdge(3, 4);
		graph.addDirectedEdge(4, 2); graph.addDirectedEdge(4, 5);
		graph.addDirectedEdge(6, 3); graph.addDirectedEdge(6, 5);
		graph.addDirectedEdge(7, 0); graph.addDirectedEdge(7, 6);
		
		System.out.println("The strongly connected components are: ");
		for ( Set<Integer> component : graph.getSCC() ) {
			System.out.println(component);
		}		
	}
	
}

final class Graph {

	public Graph(int aSize) {		
		adjacencyLists = new ArrayList<Set<Integer>>(aSize);
		for ( int i = 0; i < aSize; i++ ) {
			vertices.add(i);
			adjacencyLists.add( new HashSet<Integer>() );
		}		
	}
	
	public void addDirectedEdge(int aFrom, int aTo) {
		adjacencyLists.get(aFrom).add(aTo);
	}
	
	public List<Set<Integer>> getSCC() {
		for ( int vertex : vertices ) {
			if ( ! numbers.keySet().contains(vertex) ) {
				stronglyConnect(vertex);
			}
		}
		
		return stronglyConnectedComponents;
	}
	
	private void stronglyConnect(int aVertex) {
		numbers.put(aVertex, index);
		lowlinks.put(aVertex, index);
		index += 1;
		stack.push(aVertex);
		
		for ( int adjacent : adjacencyLists.get(aVertex) ) {
			if ( ! numbers.keySet().contains(adjacent) ) {
				stronglyConnect(adjacent);				
				lowlinks.put(aVertex, Math.min(lowlinks.get(aVertex), lowlinks.get(adjacent)));
			} else if ( stack.contains(adjacent) ) {			
				lowlinks.put(aVertex, Math.min(lowlinks.get(aVertex), numbers.get(adjacent)));
			}
		}
		
		if ( lowlinks.get(aVertex) == numbers.get(aVertex) ) {
			Set<Integer> stonglyConnectedComponent = new HashSet<Integer>();
			int top;
			do {
				top = stack.pop();
				stonglyConnectedComponent.add(top);
			} while ( top != aVertex );
						
			stronglyConnectedComponents.add(stonglyConnectedComponent);
		}
	}		
	
	private List<Set<Integer>> adjacencyLists;
	private List<Integer> vertices = new ArrayList<Integer>();	
	private int index = 0;
	private Stack<Integer> stack = new Stack<Integer>();
	private Map<Integer, Integer> numbers = new HashMap<Integer, Integer>();
	private Map<Integer, Integer> lowlinks = new HashMap<Integer, Integer>();
	private List<Set<Integer>> stronglyConnectedComponents = new ArrayList<Set<Integer>>();

}

Output:

The strongly connected components are: 
[5]
[2, 3, 4, 6]
[0, 1, 7]

jq

Works with: jq

Works with gojq, the Go implementation of jq

In this adaptation of the #Kotlin/#Wren implementations:

• a Node is represented by JSON object with .n being its id;
• a DirectedGraph is represented by a JSON object {vs, es} where vs is an array of Nodes and es is an array of integer ids;
• a Stack is reprsented by an array, with .[-1] as the active point;
• the output of `tarjan` is an array each item of which is an array of Node ids.

# Input: an integer
def Node:
  { n: .,
    index: -1,    # -1 signifies undefined
    lowLink: -1,
    onStack: false
  } ; 

# Input: a DirectedGraph
# Output: a stream of Node ids
def successors($vn): .es[$vn][];

# Input: a DirectedGraph
# Output: an array of integer arrays
def tarjan:
  . + { sccs: [],    # strongly connected components
        index: 0,
        s: []        # Stack
      }
  # input: {es, vs, sccs, index, s}      
  | def strongConnect($vn):
      # Set the depth index for v to the smallest unused index
        .vs[$vn].index = .index
      | .vs[$vn].lowLink = .index
      | .index += 1
      | .s += [ $vn ]
      | .vs[$vn].onStack = true
      
      # consider successors of v
      | reduce successors($vn) as $wn (.;
            if .vs[$wn].index < 0
	    then
                # Successor w has not yet been visited; recurse on it
                strongConnect($wn)
                | .vs[$vn].lowLink = ([.vs[$vn].lowLink, .vs[$wn].lowLink] | min )
            elif .vs[$wn].onStack
	    then
                # Successor w is in stack s and hence in the current SCC
                .vs[$vn].lowLink = ([.vs[$vn].lowLink, .vs[$wn].index] | min )
	    else .
            end
        )
      # If v is a root node, pop the stack and generate an SCC
      | if .vs[$vn] | (.lowLink == .index)
        then .scc = []
	    | .stop = false
            | until(.stop;
                .s[-1] as $wn
		| .s |= .[:-1]    # pop
                | .vs[$wn].onStack = false
                | .scc += [$wn]
                | if $wn == $vn then .stop = true else . end )
        | .sccs += [.scc]
        else .
	end
    ; 
 
    reduce .vs[].n as $vn (.;
      if .vs[$vn].index < 0
      then strongConnect($vn)
      else . end
    )
    | .sccs
;

# Vertices
def vs: [range(0;8) | Node ];

# Edges
def es:
  [ [1],
    [2],
    [0],
    [1, 2, 4],
    [5, 3],
    [2, 6],
    [5],
    [4, 7, 6]
  ]
;

{ vs: vs, es: es }
| tarjan

Output:

[[2,1,0],[6,5],[4,3],[7]]

Julia

LightGraphs uses Tarjan's algorithm by default. The package can also use Kosaraju's algorithm with the function strongly_connected_components_kosaraju().

using LightGraphs

edge_list=[(1,2),(3,1),(6,3),(6,7),(7,6),(2,3),(4,2),(4,3),(4,5),(5,6),(5,4),(8,5),(8,8),(8,7)]

grph = SimpleDiGraph(Edge.(edge_list))

tarj = strongly_connected_components(grph)

inzerobase(arrarr) = map(x -> sort(x .- 1, rev=true), arrarr)

println("Results in the zero-base scheme: $(inzerobase(tarj))")

Output:

Results in the zero-base scheme: Array{Int64,1}[[2, 1, 0], [6, 5], [4, 3], [7]]

K

Implementation:

F:{[g]
  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
  r}

Example:

F (1;2;0;1 2 4;3 5;2 6;5;4 6 7)
(0 1 2
 5 6
 3 4
 ,7)

tested with ngn/k

Kotlin

// version 1.1.3

import java.util.Stack

typealias Nodes = List<Node>

class Node(val n: Int) {
    var index   = -1  // -1 signifies undefined
    var lowLink = -1
    var onStack = false

    override fun toString()  = n.toString()
}

class DirectedGraph(val vs: Nodes, val es: Map<Node, Nodes>)

fun tarjan(g: DirectedGraph): List<Nodes> {
    val sccs = mutableListOf<Nodes>()
    var index = 0
    val s = Stack<Node>()

    fun strongConnect(v: Node) {
        // Set the depth index for v to the smallest unused index
        v.index = index
        v.lowLink = index
        index++
        s.push(v)
        v.onStack = true

        // consider successors of v
        for (w in g.es[v]!!) {
            if (w.index < 0) {
                // Successor w has not yet been visited; recurse on it
                strongConnect(w)
                v.lowLink = minOf(v.lowLink, w.lowLink)
            }
            else if (w.onStack) {
                // Successor w is in stack s and hence in the current SCC
                v.lowLink = minOf(v.lowLink, w.index)
            }
        }

        // If v is a root node, pop the stack and generate an SCC
        if (v.lowLink == v.index) {
            val scc = mutableListOf<Node>()
            do {
                val w = s.pop()
                w.onStack = false
                scc.add(w)
            }
            while (w != v)
            sccs.add(scc)
        }
    }

    for (v in g.vs) if (v.index < 0) strongConnect(v)
    return sccs
}

fun main(args: Array<String>) {
    val vs = (0..7).map { Node(it) }
    val es = mapOf(
        vs[0] to listOf(vs[1]),
        vs[2] to listOf(vs[0]),
        vs[5] to listOf(vs[2], vs[6]),
        vs[6] to listOf(vs[5]),
        vs[1] to listOf(vs[2]),
        vs[3] to listOf(vs[1], vs[2], vs[4]),
        vs[4] to listOf(vs[5], vs[3]),
        vs[7] to listOf(vs[4], vs[7], vs[6])
    )
    val g = DirectedGraph(vs, es)
    val sccs = tarjan(g)
    println(sccs.joinToString("\n"))
}

Output:

[2, 1, 0]
[6, 5]
[4, 3]
[7]

Nim

Translation of: Kotlin

import sequtils, strutils, tables

type

  Node = ref object
    val: int
    index: int
    lowLink: int
    onStack: bool

  Nodes = seq[Node]

  DirectedGraph = object
    nodes: seq[Node]
    edges: Table[int, Nodes]


func initNode(n: int): Node =
  Node(val: n, index: -1, lowLink: -1, onStack: false)


func `$`(node: Node): string = $node.val


func tarjan(g: DirectedGraph): seq[Nodes] =
  var index = 0
  var s: seq[Node]
  var sccs: seq[Nodes]


  func strongConnect(v: Node) =

    # Set the depth index for "v" to the smallest unused index.
    v.index = index
    v.lowLink = index
    inc index
    s.add v
    v.onStack = true

    # Consider successors of "v".
    for w in g.edges[v.val]:
      if w.index < 0:
        # Successor "w" has not yet been visited; recurse on it.
        w.strongConnect()
        v.lowLink = min(v.lowLink, w.lowLink)
      elif w.onStack:
        # Successor "w" is in stack "s" and hence in the current SCC.
        v.lowLink = min(v.lowLink, w.index)

    # If "v" is a root node, pop the stack and generate an SCC.
    if v.lowLink == v.index:
      var scc: Nodes
      while true:
        let w = s.pop()
        w.onStack = false
        scc.add w
        if w == v: break
      sccs.add scc


  for v in g.nodes:
    if v.index < 0:
      v.strongConnect()
  result = move(sccs)


when isMainModule:

  let vs = toSeq(0..7).map(initNode)
  let es = {0: @[vs[1]],
            1: @[vs[2]],
            2: @[vs[0]],
            3: @[vs[1], vs[2], vs[4]],
            4: @[vs[5], vs[3]],
            5: @[vs[2], vs[6]],
            6: @[vs[5]],
            7: @[vs[4], vs[7], vs[6]]}.toTable
  var g = DirectedGraph(nodes: vs, edges: es)
  let sccs = g.tarjan()
  echo sccs.join("\n")

Output:

@[2, 1, 0]
@[6, 5]
@[4, 3]
@[7]

Perl

Translation of: Raku

use strict;
use warnings;
use feature <say state current_sub>;
use List::Util qw(min);

sub tarjan {
    my (%k) = @_;
    my (%onstack, %index, %lowlink, @stack, @connected);

    my sub strong_connect {
        my ($vertex, $i) = @_;
        $index{$vertex}   = $i;
        $lowlink{$vertex} = $i + 1;
        $onstack{$vertex} = 1;
        push @stack, $vertex;
        for my $connection (@{$k{$vertex}}) {
            if (not defined $index{$connection}) {
                __SUB__->($connection, $i + 1);
                $lowlink{$vertex} = min($lowlink{$connection}, $lowlink{$vertex});
            }
            elsif ($onstack{$connection}) {
                $lowlink{$vertex} = min($index{$connection}, $lowlink{$vertex});
            }
        }
        if ($lowlink{$vertex} eq $index{$vertex}) {
            my @node;
            do {
                push @node, pop @stack;
                $onstack{$node[-1]} = 0;
            } while $node[-1] ne $vertex;
            push @connected, [@node];
        }
    }

    for (sort keys %k) {
        strong_connect($_, 0) unless $index{$_};
    }
    @connected;
}

my %test1 = (
             0 => [1],
             1 => [2],
             2 => [0],
             3 => [1, 2, 4],
             4 => [3, 5],
             5 => [2, 6],
             6 => [5],
             7 => [4, 6, 7]
            );

my %test2 = (
             'Andy' => ['Bart'],
             'Bart' => ['Carl'],
             'Carl' => ['Andy'],
             'Dave' => [qw<Bart Carl Earl>],
             'Earl' => [qw<Dave Fred>],
             'Fred' => [qw<Carl Gary>],
             'Gary' => ['Fred'],
             'Hank' => [qw<Earl Gary Hank>]
            );

print "Strongly connected components:\n";
print join(', ', sort @$_) . "\n" for tarjan(%test1);
print "\nStrongly connected components:\n";
print join(', ', sort @$_) . "\n" for tarjan(%test2);

Output:

Strongly connected components:
0, 1, 2
5, 6
3, 4
7

Strongly connected components:
Andy, Bart, Carl
Fred, Gary
Dave, Earl
Hank

Phix

Translation of: Go

Same data as other examples, but with 1-based indexes.

with javascript_semantics
constant g = {{2}, {3}, {1}, {2,3,5}, {6,4}, {3,7}, {6}, {5,8,7}}
 
sequence index, lowlink, stacked, stack
integer x
 
function strong_connect(integer n, emit)
    index[n] = x
    lowlink[n] = x
    stacked[n] = 1
    stack &= n
    x += 1
    for b=1 to length(g[n]) do
        integer nb = g[n][b]
        if index[nb] == 0 then
            if not strong_connect(nb,emit) then
                return false
            end if
            if lowlink[nb] < lowlink[n] then
                lowlink[n] = lowlink[nb]
            end if
        elsif stacked[nb] == 1 then
            if index[nb] < lowlink[n] then
                lowlink[n] = index[nb]
            end if
        end if
    end for
    if lowlink[n] == index[n] then
        sequence c = {}
        while true do
            integer w := stack[$]
            stack = stack[1..$-1]
            stacked[w] = 0
            c = prepend(c, w)
            if w == n then
                emit(c)
                exit
            end if
        end while
    end if
    return true
end function
 
procedure tarjan(sequence g, integer emit)
    index   = repeat(0,length(g))
    lowlink = repeat(0,length(g))
    stacked = repeat(0,length(g))
    stack = {}
    x = 1
    for n=1 to length(g) do
        if index[n] == 0
        and not strong_connect(n,emit) then
            return
        end if
    end for
end procedure
 
procedure emit(object c)
-- called for each component identified.
-- each component is a list of nodes.
    ?c
end procedure
 
tarjan(g,emit)

Output:

{1,2,3}
{6,7}
{4,5}
{8}

Python

Python: As function

from collections import defaultdict

def from_edges(edges):
    '''translate list of edges to list of nodes'''

    class Node:
        def __init__(self):
            # root is one of:
            #   None: not yet visited
            #   -1: already processed
            #   non-negative integer: what Wikipedia pseudo code calls 'lowlink'
            self.root = None
            self.succ = []

    nodes = defaultdict(Node)
    for v,w in edges:
        nodes[v].succ.append(nodes[w])

    for i,v in nodes.items(): # name the nodes for final output
        v.id = i

    return nodes.values()

def trajan(V):
    def strongconnect(v, S):
        v.root = pos = len(S)
        S.append(v)

        for w in v.succ:
            if w.root is None:  # not yet visited
                yield from strongconnect(w, S)

            if w.root >= 0:  # still on stack
                v.root = min(v.root, w.root)

        if v.root == pos:  # v is the root, return everything above
            res, S[pos:] = S[pos:], []
            for w in res:
                w.root = -1
            yield [r.id for r in res]

    for v in V:
        if v.root is None:
            yield from strongconnect(v, [])


tables = [  # table 1
            [(1,2), (3,1), (3,6), (6,7), (7,6), (2,3), (4,2),
             (4,3), (4,5), (5,6), (5,4), (8,5), (8,7), (8,6)],

            # table 2
            [('A', 'B'), ('B', 'C'), ('C', 'A'), ('A', 'Other')]]

for table in (tables):
    for g in trajan(from_edges(table)):
        print(g)
    print()

Output:

[6, 7]
[1, 2, 3]
[4, 5]
[8]

['Other']
['A', 'B', 'C']

Python: As class

This takes inspiration from the Geeks4Geeks explanation and uses its five examples.

Tx1

+---+     +---+     +---+     +---+
| 1 | --> | 0 | --> | 3 | --> | 4 |
+---+     +---+     +---+     +---+
  ^         |
  |         |
  |         v
  |       +---+
  +------ | 2 |
          +---+

Tx2

+---+     +---+     +---+     +---+
| 0 | --> | 1 | --> | 2 | --> | 3 |
+---+     +---+     +---+     +---+

Tx3

  +----------------------------------+
  v                                  |
+---+     +---+     +---+     +---+  |
| 0 | --> |   | --> | 3 | --> | 5 |  |
+---+     |   |     +---+     +---+  |
          |   |                 ^    |
          | 1 |                 |    |
          |   |                 |    |
+---+     |   |     +---+       |    |
| 6 | <-- |   | --> | 2 | ------+----+
+---+     +---+     +---+       |
            |                   |
            |                   |
            v                   |
          +---+                 |
          | 4 | ----------------+
          +---+

Tx4

  +-----------------------------+
  |                             |
  |       +---+                 |
  |       | A |                 |         +-------------------+
  |       +---+                 |         |                   |
  |                             |         |                   |
  |                   +---------+---------+---------+         |                   +---------+
  |                   |         v         v         v         |                   v         |
+---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
| 3 | <-- | 0 | --> | 1 | --> | 2 | --> | 6 | --> | 4 | --> |   | --> | 7 | --> | 9 | --> | 8 |
+---+     +---+     +---+     +---+     +---+     +---+     |   |     +---+     +---+     +---+
            ^                   |         ^         |       |   |                 ^         ^
            +-------------------+         +---------+       | 5 | ----------------+         |
                                                            |   |                           |
                                                            |   |                           |
                                                            |   | --------------------------+
                                                            +---+

Tx5

                      +--------------+
                      |              |
                      |              |
  +-------------------+---------+    |
  v                   v         |    |
+---+     +---+     +---+     +---+  |
| 0 | --> | 1 | --> | 2 | --> | 3 |  |
+---+     +---+     +---+     +---+  |
                      |              |
                      |              |
                      v              |
                    +---+            |
                    | 4 | -----------+
                    +---+

Code

from collections import defaultdict


class Graph:
    "Directed Graph Tarjan's strongly connected components algorithm"

    def __init__(self, name, connections):
        self.name = name
        self.connections = connections
        g = defaultdict(list)  # map node vertex to direct connections
        for n1, n2 in connections:
            if n1 != n2:
                g[n1].append(n2)
            else:
                g[n1]
        for _, n2 in connections:
            g[n2]   # For leaf nodes having no edges from themselves
        self.graph = dict(g)
        self.tarjan_algo()

    def _visitor(self, this, low, disc, stack):
        '''
        Recursive function that finds SCC's
        using DFS traversal of vertices.

        Arguments:
            this        --> Vertex to be visited in this call.
            disc{}      --> Discovery order of visited vertices.
            low{}       --> Connected vertex of earliest discovery order
            stack       --> Ancestor node stack during DFS.
        '''

        disc[this] = low[this] = self._order
        self._order += 1
        stack.append(this)

        for neighbr in self.graph[this]:
            if neighbr not in disc:
                # neighbour not visited so do DFS recurrence.
                self._visitor(neighbr, low, disc, stack)
                low[this] = min(low[this], low[neighbr])  # Prior connection?

            elif neighbr in stack:
                # Update low value of this only if neighbr in stack
                low[this] = min(low[this], disc[neighbr])

        if low[this] == disc[this]:
            # Head node found of SCC
            top, new = None, []
            while top != this:
                top = stack.pop()
                new.append(top)
            self.scc.append(new)

    def tarjan_algo(self):
        '''
        Recursive function that finds strongly connected components
        using the Tarjan Algorithm and function _visitor() to visit nodes.
        '''

        self._order = 0         # Visitation order counter
        disc, low = {}, {}
        stack = []

        self.scc = []           # SCC result accumulator
        for vertex in sorted(self.graph):
            if vertex not in disc:
                self._visitor(vertex, low, disc, stack)
        self._disc, self._low = disc, low


if __name__ == '__main__':
    for n, m in [('Tx1', '10 02 21 03 34'.split()),
                 ('Tx2', '01 12 23'.split()),
                 ('Tx3', '01 12 20 13 14 16 35 45'.split()),
                 ('Tx4', '01 03 12 14 20 26 32 45 46 56 57 58 59 64 79 89 98 AA'.split()),
                 ('Tx5', '01 12 23 24 30 42'.split()),
                 ]:
        print(f"\n\nGraph({repr(n)}, {m}):\n")
        g = Graph(n, m)
        print("               : ", '  '.join(str(v) for v in sorted(g._disc)))
        print("    DISC of", g.name + ':', [v for _, v in sorted(g._disc.items())])
        print("     LOW of", g.name + ':', [v for _, v in sorted(g._low.items())])
        scc = repr(g.scc if g.scc else '').replace("'", '').replace(',', '')[1:-1]
        print("\n   SCC's of", g.name + ':', scc)

Output:

Graph('Tx1', ['10', '02', '21', '03', '34']):

               :  0  1  2  3  4
    DISC of Tx1: [0, 2, 1, 3, 4]
     LOW of Tx1: [0, 0, 0, 3, 4]

   SCC's of Tx1: [4] [3] [1 2 0]


Graph('Tx2', ['01', '12', '23']):

               :  0  1  2  3
    DISC of Tx2: [0, 1, 2, 3]
     LOW of Tx2: [0, 1, 2, 3]

   SCC's of Tx2: [3] [2] [1] [0]


Graph('Tx3', ['01', '12', '20', '13', '14', '16', '35', '45']):

               :  0  1  2  3  4  5  6
    DISC of Tx3: [0, 1, 2, 3, 5, 4, 6]
     LOW of Tx3: [0, 0, 0, 3, 5, 4, 6]

   SCC's of Tx3: [5] [3] [4] [6] [2 1 0]


Graph('Tx4', ['01', '03', '12', '14', '20', '26', '32', '45', '46', '56', '57', '58', '59', '64', '79', '89', '98', 'AA']):

               :  0  1  2  3  4  5  6  7  8  9  A
    DISC of Tx4: [0, 1, 2, 9, 4, 5, 3, 6, 8, 7, 10]
     LOW of Tx4: [0, 0, 0, 2, 3, 3, 3, 6, 7, 7, 10]

   SCC's of Tx4: [8 9] [7] [5 4 6] [3 2 1 0] [A]


Graph('Tx5', ['01', '12', '23', '24', '30', '42']):

               :  0  1  2  3  4
    DISC of Tx5: [0, 1, 2, 3, 4]
     LOW of Tx5: [0, 0, 0, 0, 2]

   SCC's of Tx5: [4 3 2 1 0]

Racket

Manual implementation

Translation of: Kotlin

#lang racket

(require syntax/parse/define
         fancy-app
         (for-syntax racket/syntax))

(struct node (name index low-link on?) #:transparent #:mutable
  #:methods gen:custom-write
  [(define (write-proc v port mode) (fprintf port "~a" (node-name v)))])

(define-syntax-parser change!
  [(_ x:id f) #'(set! x (f x))]
  [(_ accessor:id v f)
   #:with mutator! (format-id this-syntax "set-~a!" #'accessor)
   #'(mutator! v (f (accessor v)))])

(define (tarjan g)
  (define sccs '())
  (define index 0)
  (define s '())

  (define (dfs v)
    (set-node-index! v index)
    (set-node-low-link! v index)
    (set-node-on?! v #t)
    (change! s (cons v _))
    (change! index add1)

    (for ([w (in-list (hash-ref g v '()))])
      (match-define (node _ index low-link on?) w)
      (cond
        [(not index) (dfs w)
                     (change! node-low-link v (min (node-low-link w) _))]
        [on? (change! node-low-link v (min index _))]))

    (when (= (node-low-link v) (node-index v))
      (define-values (scc* s*) (splitf-at s (λ (w) (not (eq? w v)))))
      (set! s (rest s*))
      (define scc (cons (first s*) scc*))
      (for ([w (in-list scc)]) (set-node-on?! w #f))
      (change! sccs (cons scc _))))

  (for* ([(u _) (in-hash g)] #:when (not (node-index u))) (dfs u))
  sccs)

(define (make-graph xs)
  (define store (make-hash))
  (define (make-node v) (hash-ref! store v (thunk (node v #f #f #f))))

  ;; it's important that we use hasheq instead of hash so that we compare
  ;; reference instead of actual value. Had we use the actual value,
  ;; the key would be a mutable value, which causes undefined behavior
  (for/hasheq ([vs (in-list xs)]) (values (make-node (first vs)) (map make-node (rest vs)))))

(tarjan (make-graph '([0 1]
                      [2 0]
                      [5 2 6]
                      [6 5]
                      [1 2]
                      [3 1 2 4]
                      [4 5 3]
                      [7 4 7 6])))

Output:

'((7) (3 4) (5 6) (2 1 0))

With the graph library

#lang racket

(require graph)

(define g (unweighted-graph/adj '([0 1]
                                  [2 0]
                                  [5 2 6]
                                  [6 5]
                                  [1 2]
                                  [3 1 2 4]
                                  [4 5 3]
                                  [7 4 7 6])))

(scc g)

Output:

'((7) (3 4) (5 6) (1 0 2))

Raku

(formerly Perl 6)

Works with: Rakudo version 2018.09

sub tarjan (%k) {
    my %onstack;
    my %index;
    my %lowlink;
    my @stack;
    my @connected;

    sub strong-connect ($vertex) {
         state $index      = 0;
         %index{$vertex}   = $index;
         %lowlink{$vertex} = $index++;
         %onstack{$vertex} = True;
         @stack.push: $vertex;
         for |%k{$vertex} -> $connection {
             if not %index{$connection}.defined {
                 strong-connect($connection);
                 %lowlink{$vertex} min= %lowlink{$connection};
             }
             elsif %onstack{$connection} {
                 %lowlink{$vertex} min= %index{$connection};
             }
        }
        if %lowlink{$vertex} eq %index{$vertex} {
            my @node;
            repeat {
                @node.push: @stack.pop;
                %onstack{@node.tail} = False;
            } while @node.tail ne $vertex;
            @connected.push: @node;
        }
    }

    .&strong-connect unless %index{$_} for %k.keys;

    @connected
}

# TESTING

-> $test { say "\nStrongly connected components: ", |tarjan($test).sort».sort } for

# hash of vertex, edge list pairs
(((1),(2),(0),(1,2,4),(3,5),(2,6),(5),(4,6,7)).pairs.hash),

# Same layout test data with named vertices instead of numbered.
%(:Andy<Bart>,
  :Bart<Carl>,
  :Carl<Andy>,
  :Dave<Bart Carl Earl>,
  :Earl<Dave Fred>,
  :Fred<Carl Gary>,
  :Gary<Fred>,
  :Hank<Earl Gary Hank>
)

Output:

Strongly connected components: (0 1 2)(3 4)(5 6)(7)

Strongly connected components: (Andy Bart Carl)(Dave Earl)(Fred Gary)(Hank)

REXX

/* REXX - Tarjan's Algorithm                        */
/* Vertices are numbered 1 to 8 (instead of 0 to 7) */
g='[2] [3] [1] [2 3 5] [4 6] [3 7] [6] [5 7 8]'
gg=g
Do i=1 By 1 While gg>''
  Parse Var gg '[' g.i ']' gg
  name.i=i-1
  End
g.0=i-1
index.=0
lowlink.=0
stacked.=0
stack.=0
x=1
Do n=1 To g.0
  If index.n=0 Then
    If strong_connect(n)=0 Then
      Return
  End
Exit

strong_connect: Procedure Expose x g. index. lowlink. stacked. stack. name.
Parse Arg n
index.n = x
lowlink.n = x
stacked.n = 1
Call stack n
x=x+1
Do b=1 To words(g.n)
  Call show_all
  nb=word(g.n,b)
  If index.nb=0 Then Do
    If strong_connect(nb)=0 Then
      Return 0
    If lowlink.nb < lowlink.n Then
      lowlink.n = lowlink.nb
    End
  Else Do
    If stacked.nb = 1 Then
      If index.nb < lowlink.n Then
        lowlink.n = index.nb
    end
  end
if lowlink.n=index.n then Do
  c=''
  Do z=stack.0 By -1
    w=stack.z
    stacked.w=0
    stack.0=stack.0-1
    c=name.w c
    If w=n Then Do
      Say '['space(c)']'
      Return 1
      End
    End
  End
Return 1

stack: Procedure Expose stack.
Parse Arg m
z=stack.0+1
stack.z=m
stack.0=z
Return

/* The following were used for debugging (and understanding) */

show_all: Return
ind='Index  '
low='Lowlink'
sta='Stacked'
Do z=1 To g.0
  ind=ind index.z
  low=low lowlink.z
  sta=sta stacked.z
  End
Say ind
Say low
Say sta
Return

show_stack:
ol='Stack'
Do z=1 To stack.0
  ol=ol stack.z
  End
Say ol
Return

Output:

[0 1 2]
[5 6]
[3 4]
[7]

Rust

use std::collections::{BTreeMap, BTreeSet};

// Using a naked BTreeMap would not be very nice, so let's make a simple graph representation
#[derive(Clone, Debug)]
pub struct Graph {
    neighbors: BTreeMap<usize, BTreeSet<usize>>,
}

impl Graph {
    pub fn new(size: usize) -> Self {
        Self {
            neighbors: (0..size).fold(BTreeMap::new(), |mut acc, x| {
                acc.insert(x, BTreeSet::new());
                acc
            }),
        }
    }

    pub fn edges<'a>(&'a self, vertex: usize) -> impl Iterator<Item = usize> + 'a {
        self.neighbors[&vertex].iter().cloned()
    }

    pub fn add_edge(&mut self, from: usize, to: usize) {
        assert!(to < self.len());
        self.neighbors.get_mut(&from).unwrap().insert(to);
    }

    pub fn add_edges(&mut self, from: usize, to: impl IntoIterator<Item = usize>) {
        let limit = self.len();

        self.neighbors
            .get_mut(&from)
            .unwrap()
            .extend(to.into_iter().filter(|x| {
                assert!(*x < limit);
                true
            }));
    }

    pub fn is_empty(&self) -> bool {
        self.neighbors.is_empty()
    }

    pub fn len(&self) -> usize {
        self.neighbors.len()
    }
}

#[derive(Clone)]
struct VertexState {
    index: usize,
    low_link: usize,
    on_stack: bool,
}

// The easy way not to fight with Rust's borrow checker is moving the state in
// a structure and simply invoke methods on that structure.

pub struct Tarjan<'a> {
    graph: &'a Graph,
    index: usize,
    stack: Vec<usize>,
    state: Vec<VertexState>,
    components: Vec<BTreeSet<usize>>,
}

impl<'a> Tarjan<'a> {
    // Having index: Option<usize> would look nicer, but requires just
    // some unwraps and Vec has actual len limit isize::MAX anyway, so
    // we can reserve this large value as the invalid one.
    const INVALID_INDEX: usize = usize::MAX;

    pub fn walk(graph: &'a Graph) -> Vec<BTreeSet<usize>> {
        Self {
            graph,
            index: 0,
            stack: Vec::new(),
            state: vec![
                VertexState {
                    index: Self::INVALID_INDEX,
                    low_link: Self::INVALID_INDEX,
                    on_stack: false
                };
                graph.len()
            ],
            components: Vec::new(),
        }
        .visit_all()
    }

    fn visit_all(mut self) -> Vec<BTreeSet<usize>> {
        for vertex in 0..self.graph.len() {
            if self.state[vertex].index == Self::INVALID_INDEX {
                self.visit(vertex);
            }
        }

        self.components
    }

    fn visit(&mut self, v: usize) {
        let v_ref = &mut self.state[v];
        v_ref.index = self.index;
        v_ref.low_link = self.index;
        self.index += 1;
        self.stack.push(v);
        v_ref.on_stack = true;

        for w in self.graph.edges(v) {
            let w_ref = &self.state[w];
            if w_ref.index == Self::INVALID_INDEX {
                self.visit(w);
                let w_low_link = self.state[w].low_link;
                let v_ref = &mut self.state[v];
                v_ref.low_link = v_ref.low_link.min(w_low_link);
            } else if w_ref.on_stack {
                let w_index = self.state[w].index;
                let v_ref = &mut self.state[v];
                v_ref.low_link = v_ref.low_link.min(w_index);
            }
        }

        let v_ref = &self.state[v];
        if v_ref.low_link == v_ref.index {
            let mut component = BTreeSet::new();

            loop {
                let w = self.stack.pop().unwrap();
                self.state[w].on_stack = false;
                component.insert(w);
                if w == v {
                    break;
                }
            }

            self.components.push(component);
        }
    }
}

fn main() {
    let graph = {
        let mut g = Graph::new(8);
        g.add_edge(0, 1);
        g.add_edge(2, 0);
        g.add_edges(5, vec![2, 6]);
        g.add_edge(6, 5);
        g.add_edge(1, 2);
        g.add_edges(3, vec![1, 2, 4]);
        g.add_edges(4, vec![5, 3]);
        g.add_edges(7, vec![4, 7, 6]);
        g
    };

    for component in Tarjan::walk(&graph) {
        println!("{:?}", component);
    }
}

Output:

{0, 1, 2}
{5, 6}
{3, 4}
{7}

Sidef

Translation of: Raku

func tarjan (k) {

    var(:onstack, :index, :lowlink, *stack, *connected)

    func strong_connect (vertex, i=0) {

         index{vertex}   = i
         lowlink{vertex} = i+1
         onstack{vertex} = true
         stack << vertex

         for connection in (k{vertex}) {
             if (index{connection} == nil) {
                 strong_connect(connection, i+1)
                 lowlink{vertex} `min!` lowlink{connection}
             }
             elsif (onstack{connection}) {
                 lowlink{vertex} `min!` index{connection}
             }
        }

        if (lowlink{vertex} == index{vertex}) {
            var *node
            do {
                node << stack.pop
                onstack{node.tail} = false
            } while (node.tail != vertex)
            connected << node
        }
    }

    { strong_connect(_) if !index{_} } << k.keys

    return connected
}

var tests = [
    Hash(
         0 => <1>,
         1 => <2>,
         2 => <0>,
         3 => <1 2 4>,
         4 => <3 5>,
         5 => <2 6>,
         6 => <5>,
         7 => <4 6 7>,
    ),
    Hash(
        :Andy => <Bart>,
        :Bart => <Carl>,
        :Carl => <Andy>,
        :Dave => <Bart Carl Earl>,
        :Earl => <Dave Fred>,
        :Fred => <Carl Gary>,
        :Gary => <Fred>,
        :Hank => <Earl Gary Hank>,
    )
]

tests.each {|t|
    say ("Strongly connected components: ", tarjan(t).map{.sort}.sort)
}

Output:

Strongly connected components: [["0", "1", "2"], ["3", "4"], ["5", "6"], ["7"]]
Strongly connected components: [["Andy", "Bart", "Carl"], ["Dave", "Earl"], ["Fred", "Gary"], ["Hank"]]

Wren

Translation of: Kotlin

Library: Wren-seq

Library: Wren-dynamic

import "./seq" for Stack
import "./dynamic" for Tuple

class Node {
    construct new(n) {
        _n = n
        _index = -1   // -1 signifies undefined
        _lowLink = -1
        _onStack = false
    }

    n           { _n }
    index       { _index }
    index=(v)   { _index = v }
    lowLink     { _lowLink }
    lowLink=(v) { _lowLink = v }
    onStack     { _onStack }
    onStack=(v) { _onStack = v }

    toString    { _n.toString }
}

var DirectedGraph = Tuple.create("DirectedGraph", ["vs", "es"])

var tarjan = Fn.new { |g|
    var sccs = []
    var index = 0
    var s = Stack.new()

    var strongConnect // recursive closure
    strongConnect = Fn.new { |v|
        // Set the depth index for v to the smallest unused index
        v.index = index
        v.lowLink = index
        index = index + 1
        s.push(v)
        v.onStack = true

        // consider successors of v
        for (w in g.es[v.n]) {
            if (w.index < 0) {
                // Successor w has not yet been visited; recurse on it
                strongConnect.call(w)
                v.lowLink = v.lowLink.min(w.lowLink)
            } else if (w.onStack) {
                // Successor w is in stack s and hence in the current SCC
                v.lowLink = v.lowLink.min(w.index)
            }
        }

        // If v is a root node, pop the stack and generate an SCC
        if (v.lowLink == v.index) {
            var scc = []
            while (true) {
                var w = s.pop()
                w.onStack = false
                scc.add(w)
                if (w == v) break
            }
            sccs.add(scc)
        }
    }

    for (v in g.vs) if (v.index < 0) strongConnect.call(v)
    return sccs
}

var vs = (0..7).map { |i| Node.new(i) }.toList
var es = {
    0: [vs[1]],
    2: [vs[0]],
    5: [vs[2], vs[6]],
    6: [vs[5]],
    1: [vs[2]],
    3: [vs[1], vs[2], vs[4]],
    4: [vs[5], vs[3]],
    7: [vs[4], vs[7], vs[6]]
}
var g = DirectedGraph.new(vs, es)
var sccs = tarjan.call(g)
System.print(sccs.join("\n"))

Output:

[2, 1, 0]
[6, 5]
[4, 3]
[7]

zkl

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(),
          G=List.createLong(graph.len(),0);

      // 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;
      index+=1;
      v0[ON_STACK]=True;
      stack.push(v);

       // 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
     if(w[0][INDEX]==Void){
        strongConnect(w); // Successor w not yet visited; recurse on it
        v0[LOW_LINK]=v0[LOW_LINK].min(w0[LOW_LINK]);
     }
     else if(w0[ON_STACK])
        // Successor w is in stack S and hence in the current SCC
        v0[LOW_LINK]=v0[LOW_LINK].min(w0[INDEX]);
      }
      // If v is a root node, pop the stack and generate an SCC
      if(v0[LOW_LINK]==v0[INDEX]){
         strong:=List();  // start a new strongly connected component
     do{
        w,w0 := stack.pop(), w[0];
        w0[ON_STACK]=False;
        strong.append(w[1][0]); // add w to strongly connected component
     }while(w.id!=v.id);
     components.append(strong); // output strongly connected component
      }
   }
}

   // graph from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
   // 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) );
Tarjan(graph);

Output:

0,1,2
5,6
3,4
7