Problem 48 · Graphs

Critical Connections (Tarjan Bridges)

HardClassic DSA & systems

01Problem

Given n servers and undirected connections, return all critical connections: edges whose removal disconnects some servers.

02Key insight

Tarjan's DFS tracks discovery time and low-link (earliest time reachable via a back edge). Edge (u,v) is a bridge iff low[v] > disc[u]. Use an iterative DFS for production-size graphs.

03Solution

solution.pypython34 lines

def critical_connections(n: int, connections: list[list[int]]) -> list[list[int]]:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(connections):
        graph[u].append((v, i))
        graph[v].append((u, i))
    disc = [-1] * n
    low = [0] * n
    bridges: list[list[int]] = []
    timer = 0
    for root in range(n):
        if disc[root] != -1:
            continue
        disc[root] = low[root] = timer; timer += 1
        stack = [(root, -1, iter(graph[root]))]  # (node, parent edge id, neighbor iterator)
        while stack:
            node, parent_edge, it = stack[-1]
            advanced = False
            for nxt, eid in it:
                if eid == parent_edge:
                    continue
                if disc[nxt] == -1:
                    disc[nxt] = low[nxt] = timer; timer += 1
                    stack.append((nxt, eid, iter(graph[nxt])))
                    advanced = True
                    break
                low[node] = min(low[node], disc[nxt])
            if not advanced:
                stack.pop()
                if stack:
                    parent = stack[-1][0]
                    low[parent] = min(low[parent], low[node])
                    if low[node] > disc[parent]:
                        bridges.append([parent, node])
    return bridges

Try it first.

TimeO(V+E)

SpaceO(V+E)

tests.py · 4 passing

tests.pypython4 lines

assert critical_connections(4, [[0,1],[1,2],[2,0],[1,3]]) == [[1,3]]
assert critical_connections(2, [[0,1]]) == [[0,1]]
assert sorted(map(sorted, critical_connections(5, [[0,1],[1,2],[3,4]]))) == [[0,1],[1,2],[3,4]]
assert critical_connections(3, [[0,1],[1,2],[2,0]]) == []

04Staff-level follow-up

Network topology for reliability planning: bridges are single points of failure; also compute articulation points (low[v] >= disc[u]) for single-node failures.