Tarjan's Strongly Connected Components

Low-Link & Discovery Index Formulation

Tarjan's algorithm tracks two primary integer metrics per node:

• Discovery Index (indices.get(u)): A monotonically increasing integer assigned when node $u$ is first visited.
• Low-Link Value (lowLinks.get(u)): The smallest discovery index reachable from node $u$'s DFS subtree, including back edges to nodes currently on the active stack.

When lowLinks.get(u) === indices.get(u), node $u$ is mathematically proven to be the root of an SCC. All nodes above $u$ on the stack form the complete strongly connected component.

Back-Edge Discovery Index Invariant

When traversing an edge to an already-visited target that is on the stack (a cycle back-edge), Tarjan's algorithm updates low-link using the target's discovery index, not its low-link value:

1
2
3
4
5
6
7
8
if (!indices.has(targetNodeId)) {
    // Unvisited tree edge: recurse
    strongConnect(targetNodeId);
    lowLinks.set(nodeId, Math.min(lowLinks.get(nodeId)!, lowLinks.get(targetNodeId)!));
} else if (onStack.has(targetNodeId)) {
    // Back-edge cycle found: use discovery index of target
    lowLinks.set(nodeId, Math.min(lowLinks.get(nodeId)!, indices.get(targetNodeId)!));
}