Bridges & Articulation Points
Find edges and nodes that disconnect.
Bridges & Articulation Points is a free Coding Interview Prep lesson on CoddyKit — 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, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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. 🌉
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, and the Coding Interview Prep course includes 4 lessons in total. 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.
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; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
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