Expert · Module 28 · Lesson 1 of 4
Tarjan's Strongly Connected Components (SCC), Bridges, and Articulation Points
Find all Strongly Connected Components in a directed graph and all critical bridges and cut vertices in an undirected graph in a single O(V + E) DFS pass using discovery times (tin) and low-link values (low).
By the end you can
- Maintain DFS discovery time tin[u] and low-link value low[u] in a single O(V + E) pass
- Detect undirected Bridges (low[v] > tin[u]) and Articulation Points (low[v] >= tin[u])
- Condense a directed graph's cycles into a DAG of Strongly Connected Components (SCCs) using Tarjan's stack invariant
Builds on Depth-first search, Cycles and connected components, Topological sort.
01 · A question first
In a cluster of 100,000 routers connected by 300,000 fiber links, which single fiber cut will partition the network into two disconnected islands? Removing each edge and running BFS takes 30 billion steps; Tarjan's low-link DFS finds every single critical bridge in ONE pass!
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Intuitive Explanation & Real-World Analogy
- Core Concepts & Visual Walkthrough
- Pseudocode
- Multi-Language Implementations (C++, Java, Python)
- Time & Auxiliary Space Complexity Derivation
- Edge Cases & Common Beginner Mistakes
- Alternative Approaches (Brute Force vs. Optimal)
- Pattern Recognition Guide & Three-Stage Practice Plan
03 · Practice
Something wrong with this lesson? Report a problem