Home/Algorithms/Tarjan's Strongly Connected Components

AvailablehardGraphs

Tarjan's Strongly Connected Components

Master Tarjan's Strongly Connected Components (SCC) algorithm step-by-step: Discovery Timestamps, Low-Link Values, Stack tracking, and JavaScript implementation.

Time O(V + E)Space O(V)Stable YesIn-place No

Introduction

What is Tarjan's Strongly Connected Components?

A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph where every vertex is reachable from every other vertex in the component.

Tarjan's Algorithm finds all SCCs in a directed graph in a single DFS pass by assigning discovery times and tracking low-link values using an execution stack.

Algorithm Overview

How it works

1
Initialize Discovery and Low-Link Arrays
Track discovery time ids[u], lowest reachable node low[u], and keep an execution stack stack.
2
DFS Traversal
For an unvisited node u, set ids[u] = low[u] = ++timer, push u onto stack, and mark onStack[u] = true.
3
Update Low-Link Values
For each neighbor v of u: if unvisited, recurse DFS(v) then low[u] = min(low[u], low[v]). If v is already on stack, low[u] = min(low[u], ids[v]).
4
Extract SCC Node Group
If ids[u] === low[u], u is the root of an SCC! Pop nodes from stack until u is popped; all popped nodes form one SCC component.

tarjanSCC.js

1function findSCCs(n, graph) {
2  let timer = 0;
3  const ids = new Array(n).fill(-1);
4  const low = new Array(n).fill(-1);
5  const onStack = new Array(n).fill(false);
6  const stack = [];
7  const sccs = [];
8 
9  function dfs(u) {
10    ids[u] = low[u] = ++timer;
11    stack.push(u);
12    onStack[u] = true;
13 
14    for (const v of graph[u] || []) {
15      if (ids[v] === -1) {
16        dfs(v);
17        low[u] = Math.min(low[u], low[v]);
18      } else if (onStack[v]) {
19        low[u] = Math.min(low[u], ids[v]);
20      }
21    }
22 
23    // Root of an SCC found
24    if (ids[u] === low[u]) {
25      const currentSCC = [];
26      while (true) {
27        const node = stack.pop();
28        onStack[node] = false;
29        currentSCC.push(node);
30        if (node === u) break;
31      }
32      sccs.push(currentSCC);
33    }
34  }
35 
36  for (let i = 0; i < n; i++) {
37    if (ids[i] === -1) dfs(i);
38  }
39 
40  return sccs;
41}
42 
43// Example usage:
44// 5 vertices (0 to 4)
45// const graph = {
46//   0: [1],
47//   1: [2],
48//   2: [0, 3],
49//   3: [4],
50//   4: []
51// };
52// findSCCs(5, graph); // Returns [[4], [3], [2, 1, 0]]

Interactive Quiz

Test your knowledge

Practice Problems

Solve top interview questions

Coming Next

Interactive features on the way

The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.

Next update

Low-Link Value Tracker

This feature will be implemented in the next update.

Next update

Stack Pop Component Highlighter

This feature will be implemented in the next update.

Next update

Kosaraju Algorithm Comparison

This feature will be implemented in the next update.

Back to all algorithms

Explore the full catalog — 30+ algorithms with more unlocking every release.

Browse Algorithms

Home/Algorithms/Tarjan's Strongly Connected Components

AvailablehardGraphs

Tarjan's Strongly Connected Components

Master Tarjan's Strongly Connected Components (SCC) algorithm step-by-step: Discovery Timestamps, Low-Link Values, Stack tracking, and JavaScript implementation.

Time O(V + E)Space O(V)Stable YesIn-place No

Introduction

What is Tarjan's Strongly Connected Components?

A Strongly Connected Component (SCC) of a directed graph is a maximal subgraph where every vertex is reachable from every other vertex in the component.

Tarjan's Algorithm finds all SCCs in a directed graph in a single DFS pass by assigning discovery times and tracking low-link values using an execution stack.

Algorithm Overview

How it works

1
Initialize Discovery and Low-Link Arrays
Track discovery time ids[u], lowest reachable node low[u], and keep an execution stack stack.
2
DFS Traversal
For an unvisited node u, set ids[u] = low[u] = ++timer, push u onto stack, and mark onStack[u] = true.
3
Update Low-Link Values
For each neighbor v of u: if unvisited, recurse DFS(v) then low[u] = min(low[u], low[v]). If v is already on stack, low[u] = min(low[u], ids[v]).
4
Extract SCC Node Group
If ids[u] === low[u], u is the root of an SCC! Pop nodes from stack until u is popped; all popped nodes form one SCC component.

tarjanSCC.js

1function findSCCs(n, graph) {
2  let timer = 0;
3  const ids = new Array(n).fill(-1);
4  const low = new Array(n).fill(-1);
5  const onStack = new Array(n).fill(false);
6  const stack = [];
7  const sccs = [];
8 
9  function dfs(u) {
10    ids[u] = low[u] = ++timer;
11    stack.push(u);
12    onStack[u] = true;
13 
14    for (const v of graph[u] || []) {
15      if (ids[v] === -1) {
16        dfs(v);
17        low[u] = Math.min(low[u], low[v]);
18      } else if (onStack[v]) {
19        low[u] = Math.min(low[u], ids[v]);
20      }
21    }
22 
23    // Root of an SCC found
24    if (ids[u] === low[u]) {
25      const currentSCC = [];
26      while (true) {
27        const node = stack.pop();
28        onStack[node] = false;
29        currentSCC.push(node);
30        if (node === u) break;
31      }
32      sccs.push(currentSCC);
33    }
34  }
35 
36  for (let i = 0; i < n; i++) {
37    if (ids[i] === -1) dfs(i);
38  }
39 
40  return sccs;
41}
42 
43// Example usage:
44// 5 vertices (0 to 4)
45// const graph = {
46//   0: [1],
47//   1: [2],
48//   2: [0, 3],
49//   3: [4],
50//   4: []
51// };
52// findSCCs(5, graph); // Returns [[4], [3], [2, 1, 0]]

Interactive Quiz

Test your knowledge