Start here (middle school). Picture a group chat where messages travel only one way: A can call B, B can call C, and so on. A strongly connected group is a set of people where, starting from anyone, a message can reach everyone else and still find its way back. On a one-way street map it is the set of intersections you can drive away from and still return to. Tarjan's algorithm finds every such group in a single walk through the graph.
Number the nodes as you meet them (high school). Explore the graph depth-first. The first node you visit gets discovery number disc = 0, the next brand-new one gets 1, and so on. Keep every node you are still “inside” on a stack. For each node also track a low-link value low: the smallest discovery number it can still reach without leaving the stack. At first low[u] = disc[u].
Pull the low-link down. Following an edge u → v where v is still on the stack lets u reach v's discovery time, so low[u] = min(low[u], disc[v]). Worked example: the walk visits A(0) → B(1) → C(2), and C has an edge back to A. That back edge pulls C's low-link down to 0; as the walk unwinds, B and A settle at 0 as well. All three now share the lowest reachable number, so they form one component.
When does a group close? (AP / intro-college). After exploring everything below a node u, check whether low[u] still equals disc[u]. If it does, nothing beneath u found a way back to an earlier node, so u is the root of a component: pop the stack down to u and that pile is one SCC. In a graph with no cycles (a DAG) every node closes alone, so each vertex is its own SCC. Because the walk touches each node and each edge exactly once, the whole run is O(V + E).
Try this. Press Step and watch the highlighted pseudocode line and the step counter move together — each highlighted line is one action of the walk described above. (Note: the animation panel above is a generic step-through visualizer shared across these pages; a live SCC graph animation is still being built, so use the pseudocode in §1 and the worked example here to follow the real Tarjan logic.)
§3 — Complexity Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity
W(n)
Worst case
A(n)
Average case
Step 1 -- Strongly Connected Components. A strongly connected component (SCC) is a maximal set of vertices where every vertex can reach every other vertex. Every directed graph has a unique partition into SCCs. The condensation (DAG of SCCs) is a useful structure.
Step 2 -- Discovery and Low-Link Values. disc[u] = discovery time of u in DFS. low[u] = smallest discovery time reachable from the subtree rooted at u via DFS tree edges AND at most ONE back edge. low[u] = disc[u] means u is the root of an SCC.
Step 3 -- Stack for SCC Membership. DFS stack tracks vertices in current DFS path. onStack[v] is true if v is in the current DFS stack. When low[u]==disc[u]: pop all vertices from stack until (and including) u -- these form one SCC.
Step 4 -- Time O(V+E). Each vertex processed once: O(V). Each edge traversed once: O(E). Total: O(V+E). Same as a single DFS.
Step 5 -- Correctness. low[u]==disc[u] iff u is the root of an SCC (no back edge from u's subtree can reach u's ancestor). All vertices in the current SCC are above u on the stack.
Step 6 -- Applications. Condensation DAG for cycle detection. 2-SAT (satisfiability of 2-literal clauses -- each clause is an implication, SCCs represent equivalent literals). Finding cycles in dependency graphs. Compiler optimization (loop detection). Social network community detection.
§4 — Frequently Asked Questions
What is a strongly connected component? concept+
SCC: maximal set where every vertex can reach every other via directed paths. Single vertices with no self-loop are trivially SCCs. A DAG's SCCs are all individual vertices. A cycle is one big SCC.
What is the low-link value? concept+
low[u] = minimum discovery time reachable from u's DFS subtree via tree edges and at most one back edge. Key: when DFS tree child v returns low[v], update low[u]=min(low[u],low[v]). When back edge (u,v) found and v is on stack: low[u]=min(low[u],disc[v]).
Why only update low[u] if v is on stack? concept+
If v is NOT on the stack, v is already in a completed SCC. Its back edge doesn't connect u's SCC to that completed SCC -- they are separate SCCs. Updating low with off-stack vertices would incorrectly merge SCCs.
How does Tarjan's compare to Kosaraju's algorithm? applied+
Kosaraju: two DFS passes (original + transposed graph). Simpler conceptually but requires building transposed graph. Tarjan: one DFS pass, more complex but faster constant. Both O(V+E). Tarjan's is preferred in competitive programming for its single pass.
What is 2-SAT and how does it use SCCs? deep+
2-SAT: given clauses of form (a OR b), find satisfying assignment. Model as implication graph: (a OR b) = (NOT a => b) AND (NOT b => a). Find SCCs. If any variable x and NOT x are in same SCC: UNSATISFIABLE. Otherwise: assign values based on SCC topological order. O(V+E) via Tarjan's.
What is the condensation of a directed graph? nonobv+
Contract each SCC into a single node. The resulting graph is a DAG (no cycles -- each cycle is inside an SCC). The condensation reveals the high-level structure. Useful for: reachability queries, transitive closure compression, dependency analysis.
§5 — Misconceptions & Errors
Conceptual Misconceptions
✗ Every vertex is in exactly one SCC.
✓ True -- every directed graph has a unique partition of vertices into SCCs. Even isolated vertices form singleton SCCs.
✗ Tarjan's algorithm finds SCCs in topological order.
✓ Tarjan's outputs SCCs in REVERSE topological order of the condensation DAG (the first SCC found is a sink SCC). To get topological order, reverse the output.
✗ A vertex with no edges is not an SCC.
✓ A single vertex with no edges is a singleton SCC. By definition, every vertex can trivially reach itself (empty path of length 0).
Implementation Errors
✗ Updating low[u] with disc[v] even when v is not on stack.
✓ Must check onStack[v]. Off-stack vertices are in completed SCCs. Including them falsely merges current SCC with a finished one.
✗ Confusing low[u] with the minimum disc in the entire subtree.
✓ low[u] = minimum reachable via tree edges + ONE back edge. It's NOT the minimum disc in the entire subtree reachable via multiple back edges.
✗ Forgetting onStack[] -- relying only on visited[].
✓ visited[v] true means v is in some completed SCC (might be off-stack). onStack[v] true means v is on the current DFS stack -- only these back edges affect low values.