Algorithms / Bridges Articulation

Least You Need to Know: Bridges, Articulation Points, and Fragile Connectivity

Bridges and articulation points identify where an undirected graph is **fragile**. A bridge is an edge whose removal disconnects the graph; an articulation point is a vertex whose removal does the same.

جو کم از کم جاننا ضروری ہے

Bridges are cut edges in undirected graphs.
Articulation points are cut vertices in undirected graphs.
Both concepts detect single-point failures in connectivity.
DFS low-link reasoning reveals whether back edges bypass a tree edge or vertex.
Tree edges with no alternate return route indicate vulnerability.

اہم علامتیں

disc[u] DFS discovery time of u

low[u] lowest discovery time reachable from u via tree edges plus at most one back edge

bridge edge whose deletion increases connected-component count

مختصر حل شدہ مثال

If DFS goes from `u` to child `v` and the subtree under `v` cannot reach any ancestor of `u`, then edge `(u, v)` is a bridge.
Intuitively, there is no alternate route around that edge.
The same style of reasoning identifies articulation points when removing a vertex separates child subtrees.
Low-link values summarize whether such alternate routes exist.

عام غلطیاں

Bridges and articulation points are usually defined for undirected graphs.
A vertex on a cycle is often not an articulation point because the cycle provides an alternate route.
The DFS root has a special articulation-point rule involving multiple children.

اس قسم کے سوال کو کیسے پہچانیں

The problem asks about single edge or single vertex failures.
You need to know whether a DFS subtree can reconnect upward without using its parent edge.
Low-link or Tarjan-style DFS is suggested.