DSA Notes

Graphs

Bridges & Articulation Points

Find the edges and vertices whose removal disconnects the graph.

The idea

A bridge is an edge whose removal splits the graph; an articulation point is a vertex with the same effect.

Run one DFS and record num[u], the time u was first visited, and low[u], the smallest num reachable from u’s subtree using at most one edge that goes back up.

A tree edge u → v is a bridge when low[v] > num[u]: nothing below v reaches u or above. A non-root u is an articulation point when some child has low[v] ≥ num[u]; the root is one when it has two or more DFS children.

Sample problem

1192. Critical Connections in a Network ↗ Hard

Servers are connected by undirected links, and the network is connected. A link is critical if removing it disconnects some servers. Return all critical links.

n = 5, connections = [[0,1],[1,2],[2,0],[1,3],[3,4]]
output = [[3,4],[1,3]]

Why the solution works

Removing each link and testing connectivity is O(E · (V + E)). One DFS is enough.

The DFS turns the graph into a tree plus edges that jump back up to an ancestor. A tree edge u → v survives being removed only if something in v’s subtree can jump back to u or above.

low[v] records the highest point that subtree can reach. If low[v] > num[u], it cannot reach u, and the edge u–v is a bridge.

Complexity: O(V + E) time and memory.

Watch out

  • With parallel edges, skipping by parent vertex is wrong: skip the edge you came along by its id.
  • The root needs its own rule for articulation points.
  • Update low with num[v] on a back edge and with low[v] after a tree edge.
Watch it run

Practise on LeetCode