Tarjan SCC
Find strongly connected components in one DFS by tracking discovery times, low-link values, and the active stack.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
Step 1 / 6
| node | disc | low |
|---|---|---|
| 0 | 0 | 0 |
| 1 | - | - |
| 2 | - | - |
| 3 | - | - |
| 4 | - | - |
| 5 | - | - |
Tarjan stack
Low-link values decide SCC roots
Start DFS at 0 and push it onto the stack.
Family
Graphs
Nodes, edges, traversal, connectivity, and shortest paths.
Builds on
2 topics
Read these first if you want the surrounding context.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
In a directed graph, a strongly connected component is a maximal set of vertices where every node can reach every other node.
You want to partition the graph into these SCCs efficiently.
Core idea
Tarjan runs one DFS and maintains:
disc[u]: discovery timelow[u]: earliest discovery time reachable while staying inside the current DFS stack context- a stack of nodes that belong to the current unresolved SCCs
When low[u] == disc[u], node u is the root of one SCC, so everything on the stack up to u pops together.
Why it works
The stack represents nodes still “open” in the DFS search tree. Low-link values tell you whether a subtree can reach an ancestor that is also still open.
If it cannot, that subtree has just closed into one SCC.
Algorithm sketch
- DFS into an unvisited node
- assign
discandlow - push the node onto the active stack
- update
lowfrom tree edges and back edges to nodes still on the stack - when
low[u] == disc[u], pop one whole SCC
Complexity
| Operation | Time |
|---|---|
| Full SCC decomposition |
Key takeaways
- Tarjan finds SCCs in one DFS pass
- The stack matters: only edges to nodes still on the stack can shrink low-link values for SCC detection
low[u] == disc[u]means “this node closes a component”- This is a rare advanced graph topic, but it is foundational for serious directed-graph work
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Planets and Kingdoms | 🔴 Hard | Build SCC decomposition |
| Calling Circles | 🔴 Hard | Classic SCC grouping |
| 2-SAT references | 🔴 Hard | SCCs on implication graphs |
Relation to other topics
- DFS supplies the search tree and timestamps
- Topological Sort often appears after SCC condensation into a DAG
- Bridges & Articulation Points use related low-link ideas, but on undirected graphs
Build on these first
These topics supply the mental model or underlying structure that this page assumes.
DFS — Depth-First Search
Dive as deep as possible before backtracking. DFS is essential for detecting cycles, topological sorting, and exploring all paths in a graph.
Graph Fundamentals
Learn the core language of nodes, edges, paths, and cycles. Graphs are the broad container that trees, BFS, DFS, Dijkstra, and MST all live inside.
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
Topological Sort
Order the nodes of a DAG so that every edge points forward. Essential for dependency resolution, build systems, and scheduling.
Union-Find (Disjoint Set)
Track connected components efficiently with near-constant time union and find operations. The backbone of Kruskal's MST and dynamic connectivity.
Bridges and Articulation Points
Use DFS timestamps and low-link values to find the edges and vertices whose removal disconnects an undirected graph.
DSU Rollback
Add an undo stack to Union-Find so merges can be reversed during offline divide-and-conquer or time-travel style processing.
More from Graphs
Stay in the same family when you want parallel variations of the same mental model.
BFS — Breadth-First Search
Explore a graph level by level using a queue. BFS finds the shortest path in unweighted graphs and is fundamental to many graph algorithms.
DFS — Depth-First Search
Dive as deep as possible before backtracking. DFS is essential for detecting cycles, topological sorting, and exploring all paths in a graph.
Graph Fundamentals
Learn the core language of nodes, edges, paths, and cycles. Graphs are the broad container that trees, BFS, DFS, Dijkstra, and MST all live inside.
0-1 BFS
Find shortest paths in graphs whose edge weights are only 0 or 1 using a deque instead of a heap.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
Graph toolkit
Start with graph shape, then layer traversal, connectivity structure, and both single-source and all-pairs path algorithms.
Graph structure
Go beyond traversal into SCCs, critical edges, degree structure, and other non-shortest-path graph properties.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.