Lesson 293
Articulation Points & Bridges
disc & low in one DFS
1:00How to find every single point of failure in a graph — cut vertices and bridge edges — in one O(V + E) depth-first search using discovery times and low-link values.
By the end, you can
- Explain the difference between an articulation point and a bridge.
- Trace the Tarjan DFS on a small graph, computing disc and low values for each vertex.
- Apply the bridge condition (`low[v] > disc[u]`) to identify bridge edges.
- Apply the cut-vertex condition (`low[v] >= disc[u]`) to identify articulation points in non-root vertices.
- Explain why the root requires a separate children-count rule and why the standard condition fails for it.
- Justify why the parent edge must be skipped (not treated as a back edge) in an undirected graph.
- State the time complexity of the single-DFS approach and compare it to brute force.
Up next in String Algorithms, Advanced DP & Competitive Techniques
