Graph Theory37 sections · 1633 units
Open in Course

Problem - Critical Connections

LeetCode 1192 - Finding bri...

You have n servers connected by cables. Some cables are critical: if you remove one, some servers become unreachable. Find all critical cables. Return them as a list of edges.

This is a classic application of bridge-finding algorithms like Tarjan's. Run a single DFS and track discovery times and low-link values. An edge (u,v)(u,v) is a bridge if low[v] > disc[u]. This means the subtree rooted at vv has no back edge reaching above uu, so removing (u,v)(u,v) disconnects vv's subtree.