DSA Critical Connections (Bridges)

The problem

A network has n nodes and a list of undirected connections between them. A bridge is a connection whose removal splits its part of the network into two separate parts. The task lists every bridge.

Connections on a cycle are never bridges, because traffic can go the other way around. Connections forming the only path between two areas always are bridges.

cases = [
    (4, [[0, 1], [1, 2], [2, 0], [1, 3]], [[1, 3]]),
    (5, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]], [[2, 3], [3, 4]]),
    (3, [[0, 1], [1, 2], [2, 0]], []),
    (2, [[0, 1]], [[0, 1]]),
]
for n, conns, expected in cases:
    print("nodes:", n, "connections:", conns, "bridges:", expected)

The first network is a triangle with one tail connection. Only the tail is a bridge. The second network extends the tail, and both tail connections become bridges.

Intuition: an edge is safe when a way around exists

The first idea looks for a way around each connection. A connection inside a cycle has an alternate route between its ends. A connection with no alternate route carries everything between its two sides.

Checking one connection at a time is easy to picture. Doing it naively means re-testing the whole network for every connection. The next section runs exactly that test and counts its price.

graph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1]}
def reachable_without(start, goal, banned):
    seen = {start}
    stack = [start]
    while stack:
        u = stack.pop()
        if u == goal:
            return True
        for v in graph[u]:
            if (u, v) == banned or (v, u) == banned:
                continue
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return False

print("1 to 2 without edge 1-2:", reachable_without(1, 2, (1, 2)))
print("1 to 3 without edge 1-3:", reachable_without(1, 3, (1, 3)))

The triangle gives 1 and 2 a way around through 0. The tail node 3 has no way around at all. Alternate-route existence is the whole question, asked once per connection.

Brute force: remove each edge and test the network

The brute force removes one connection, then walks the network from node 0 and counts reached nodes. A connection whose removal strands any node in its component is a bridge. The test repeats for every connection.

def bridges_brute(n, connections):
    checks = [0]
    def reached(start, banned_index):
        graph = {i: [] for i in range(n)}
        for idx, (u, v) in enumerate(connections):
            if idx == banned_index:
                continue
            graph[u].append(v)
            graph[v].append(u)
        seen = {start}
        stack = [start]
        while stack:
            u = stack.pop()
            checks[0] += 1
            for w in graph[u]:
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        return seen
    full = reached(0, -1)
    found = []
    for idx, (u, v) in enumerate(connections):
        if reached(0, idx) != full:
            found.append([u, v])
    return sorted(found), checks[0]

for n, conns in [(4, [[0, 1], [1, 2], [2, 0], [1, 3]]),
                 (5, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]])]:
    found, checks = bridges_brute(n, conns)
    print("nodes:", n, "bridges:", found, "node visits across all tests:", checks)

The answers match, and the visit counts show the repetition. Each connection triggers a fresh walk over the same nodes. One deep walk can answer for all connections at once, which is what the optimal method does.

The optimal solution: discovery times and low-links

Depth-first search numbers each node with its discovery time, the step when the search first reaches it, and each node also earns a low-link, the smallest discovery time reachable from it through tree edges and one back edge. An edge to a child is a bridge exactly when the child's low-link stays above the parent's discovery time.

A back edge is an edge joining a node to an ancestor, a node on the search path above it. A child subtree with a back edge reaching above its parent gives the parent edge a way around. Neighbours are visited in sorted order, so the printed times are reproducible.

def bridges(n, connections):
    graph = {i: [] for i in range(n)}
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    for u in graph:
        graph[u].sort()
    disc = [-1] * n
    low = [0] * n
    found = []
    timer = [1]
    visits = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        visits[0] += 1
        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    found.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    for start in range(n):
        if disc[start] == -1:
            dfs(start, -1)
    return sorted(found), disc, low, visits[0]

for n, conns in [(4, [[0, 1], [1, 2], [2, 0], [1, 3]]),
                 (5, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]]),
                 (3, [[0, 1], [1, 2], [2, 0]]),
                 (2, [[0, 1]])]:
    found, disc, low, visits = bridges(n, conns)
    print("nodes:", n, "discovery:", disc, "low-links:", low, "bridges:", found)

Every triangle node carries low-link 1, because the cycle reaches back to the start. Tail nodes keep their own discovery times as low-links. Those rows are the bridge test, already answered.

Walkthrough: the triangle with a tail

The walk searches the first network in sorted neighbour order. Node 0 discovers first, then 1, then 2, then the tail node 3. The table below applies the bridge test to each tree edge after the search.

def bridges(n, connections):
    graph = {i: [] for i in range(n)}
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    for u in graph:
        graph[u].sort()
    disc = [-1] * n
    low = [0] * n
    found = []
    timer = [1]
    visits = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        visits[0] += 1
        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    found.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    for start in range(n):
        if disc[start] == -1:
            dfs(start, -1)
    return sorted(found), disc, low, visits[0]

found, disc, low, visits = bridges(4, [[0, 1], [1, 2], [2, 0], [1, 3]])
print("discovery times:", disc)
print("low-links:", low)
for parent, child in [(0, 1), (1, 2), (1, 3)]:
    print("edge", parent, "-", child, ": child low-link", low[child],
          "> parent discovery", disc[parent], "?", low[child] > disc[parent])
print("bridges:", found)

Only the tail edge passes the test, with low-link 4 above discovery time 2. The triangle edges fail it, because their child subtrees reach back to time 1. The answer reads straight off the two arrays.

Complexity

The single search visits each node and each connection once, so its time is O(n plus e) for n nodes and e connections. Its arrays hold one entry per node, plus the graph, so its space is O(n plus e).

The brute force repeats a full walk per connection. Its time is O(e times (n plus e)), and the counted visits below show the multiplier at work.

def brute_visits(n):
    connections = [[i, i + 1] for i in range(n - 1)]
    visits = 0
    for banned in range(-1, len(connections)):
        graph = {i: [] for i in range(n)}
        for idx, (u, v) in enumerate(connections):
            if idx == banned:
                continue
            graph[u].append(v)
            graph[v].append(u)
        seen = {0}
        stack = [0]
        while stack:
            u = stack.pop()
            visits += 1
            for w in graph[u]:
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
    return visits

for n in [5, 10, 20]:
    print("path nodes", n, "- brute visits:", brute_visits(n),
          " single-search visits:", n)

On a path of 20 nodes the brute force visits 210 nodes to learn what one 20-node search knows. Every path edge is a bridge, so the repeated walks buy no shortcut. The gap grows with both dimensions of the network.

Edge cases and pitfalls

A disconnected network breaks a careless search that starts only at node 0. Nodes in other components never get discovery times, and their bridges go unreported. This article's search restarts at every unvisited node.

Treating the parent edge as a back edge is the second classic bug. It lowers every low-link to the parent's time and hides every bridge. The search skips the parent explicitly for that reason.

def bridges(n, connections):
    graph = {i: [] for i in range(n)}
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    for u in graph:
        graph[u].sort()
    disc = [-1] * n
    low = [0] * n
    found = []
    timer = [1]
    visits = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        visits[0] += 1
        for v in graph[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    found.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    for start in range(n):
        if disc[start] == -1:
            dfs(start, -1)
    return sorted(found), disc, low, visits[0]

print("two triangles:", bridges(6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3]])[0])
print("two triangles joined:", bridges(6, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3]])[0])
print("single node:", bridges(1, []))
print("one edge:", bridges(2, [[0, 1]])[0])

Two separate triangles report no bridges, and the search still covers both. Joining them with one connection makes exactly that connection a bridge. The restart rule is what puts the second triangle's edges under the same test.