Bridges & Articulation Points
Find edges and nodes that disconnect.
Bridges & Articulation Points is a free Coding Interview Prep lesson on CoddyKit. This is lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
Fragile Spots in a Graph
Some parts of an undirected graph are critical: remove them and the graph splits apart. Finding them reveals weak links.
What a Bridge Is
A bridge is an edge whose removal increases the number of connected components. It is the only path between two regions.
What an Articulation Point Is
An articulation point is a node whose removal disconnects the graph. Networks fear these single points of failure.
DFS Trees Again
Both run on one DFS, tracking discovery time and a low value, much like Tarjan but on an undirected graph.
disc = [-1] * n
low = [-1] * nLow Means Highest Reach
A node's low is the earliest discovery id reachable from its DFS subtree, possibly via one back edge upward.
Initialize on Entry
When DFS enters a node, stamp its disc and low to the current timer and move forward into its neighbors.
disc[u] = low[u] = timer
timer += 1The Bridge Condition
After recursing into child v, if low[v] > disc[u], no back edge skips past u, so edge u-v is a bridge.
if low[v] > disc[u]:
bridges.append((u, v))The Articulation Condition
A non-root u is an articulation point when a child v satisfies low[v] >= disc[u]: v's subtree cannot bypass u.
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)The Root Special Case
The DFS root is an articulation point only if it has two or more children in the DFS tree, so count them.
if parent[u] == -1 and children > 1:
art.add(u)Skip the Parent Edge
When updating low from a back edge, do not bounce back along the edge to your parent, or you will misjudge bridges.
if v != parent[u]:
low[u] = min(low[u], disc[v])One Pass, Both Answers
A single DFS finds every bridge and articulation point together in O(V + E). No extra traversal is needed.
Quick Check
After recursing into child v from u, you find low[v] > disc[u]. What have you found?
Recap: Critical Edges & Nodes
One DFS with disc and low finds it all: low[v] > disc[u] marks a bridge, and low[v] >= disc[u] marks an articulation point. 🌉
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “Bridges & Articulation Points” lesson free?
Yes — the full text of “Bridges & Articulation Points” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “Bridges & Articulation Points”?
Find edges and nodes that disconnect. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 4 of 4.
How long does the “Bridges & Articulation Points” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Topological Sort with Kahn's Algorithm
- Detect Cycles in Directed Graphs
- Strongly Connected Components
- Bridges & Articulation Points