Critical Connections in a Network
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
n servers joined by two-way connections (a connected network). Return all connections whose removal would disconnect some servers (bridges).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1In a cycle, can a single road be critical?
- Hint 2Record the order in which nodes are first visited and the lowest order reachable from each node's subtree.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A city's road network. Walk through the city (depth-first) writing in a diary the time you first reach each junction. For every junction also note the earliest-visited junction you can get back to without using the road you came by. Now look at a road from junction A to a new junction B: if from B's side (the whole area explored beyond B) the earliest you can get back is B itself or later, nothing connects that area to A's side except this road. Close it and that area is cut off: it is a bridge.
- The obvious way
Remove each connection and test whether the network is still connected: O(edges x (n + edges)).
- The key insight
DFS from node 0, giving each node an arrival number. For each node keep lowest = the smallest arrival number reachable using its subtree plus at most one back edge (not the edge to its parent). When returning from a child: lowest[node] = min(lowest[node], lowest[child]); and if lowest[child] > arrival[node], the child side cannot reach node or earlier: the edge (node, child) is a bridge.
- The algorithm
- Build neighbour lists. arrival = -1 (unvisited).
- Visit a node: arrival = lowest = clock; clock + 1.
- For each neighbour except the parent: unvisited = go deeper; visited = lowest = min(lowest, its arrival).
- After returning from a child: update lowest; if lowest[child] > arrival[node], record the bridge.
Watch it run
Examplen = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Visit 0 (arrival 0), then 1 (arrival 1), then 2 (arrival 2).
arrival: 0, 1, 2
Where people slip
- Skip only the edge back to the parent; other visited neighbours are back edges and lower the lowest value.
- Very deep networks can overflow a recursive DFS; the Python version above is iterative for that reason.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def critical_connections(n, connections):
neighbours = [[] for _ in range(n)]
for first, second in connections:
neighbours[first].append(second)
neighbours[second].append(first)
arrival = [-1] * n # when each junction was first reached
lowest = [0] * n # earliest arrival reachable from its area
bridges = []
arrival[0] = lowest[0] = 0
clock = 1
walk = [(0, -1, iter(neighbours[0]))] # (junction, road we came by, roads left to try)
while walk:
junction, parent, pending = walk[-1]
went_deeper = False
for friend in pending:
if friend == parent:
continue
if arrival[friend] == -1:
arrival[friend] = lowest[friend] = clock
clock += 1
walk.append((friend, junction, iter(neighbours[friend])))
went_deeper = True
break
lowest[junction] = min(lowest[junction], arrival[friend]) # a way back to an earlier junction
if not went_deeper:
walk.pop()
if walk:
above = walk[-1][0]
lowest[above] = min(lowest[above], lowest[junction])
if lowest[junction] > arrival[above]:
bridges.append([above, junction]) # nothing else links this area back
return bridgesNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.