Workspace

Problem workspace

3 day streakD

Bridges in an Undirected Graph

HardGraphsConnectivity

The challenge

Find every edge in an undirected graph whose removal increases the number of connected components.

Use edge IDs to distinguish parallel edges. Skip the exact parent edge, not every edge to the parent vertex.

Example

C–D and D–E are bridges. Edges around A–B–C–F–A lie on a cycle, so removing any one of them leaves another route.

Use the walkthrough below to inspect the input and each state change.

See Bridges, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 6 edgesA = 0, B = 1, …
Connected graphUndirected graph with 6 vertices. Initialize discovery and low-link values. low[u] is the earliest discovery reachable from u’s DFS subtree using tree edges and at most one back edge. Skip the parent edge by ID. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisited
Discovery / low-link
ABCDEF
——————
Step 01 / 15

Initialize discovery and low-link values.

low[u] is the earliest discovery reachable from u’s DFS subtree using tree edges and at most one back edge. Skip the parent edge by ID.

discovery = [-1] * V; timer = 0

DFS path · top last

Empty
View input edges

A — B · A — F · B — C · C — F · C — D · D — E

Put it into code

A child subtree needs a back route to the parent or an ancestor to avoid a bridge.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

def find_cuts(n, edges):
    # Undirected edges listed ONCE as (u, v).
    # Edge IDs make parallel edges safe.
    adj = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        adj[u].append((v, edge_id))
        adj[v].append((u, edge_id))
    discovery, low = [-1] * n, [-1] * n
    bridges, articulation = [], set()
    timer = 0

    def visit(u, parent_edge=-1):
        nonlocal timer
        discovery[u] = low[u] = timer
        timer += 1
        children = 0
        for v, edge_id in adj[u]:
            if edge_id == parent_edge:
                continue
            if discovery[v] == -1:
                children += 1
                visit(v, edge_id)
                low[u] = min(low[u], low[v])
                if low[v] > discovery[u]:
                    bridges.append(edge_id)
                if parent_edge != -1 and low[v] >= discovery[u]:
                    articulation.add(u)
            else:
                low[u] = min(low[u], discovery[v])
        if parent_edge == -1 and children > 1:
            articulation.add(u)

    for u in range(n):
        if discovery[u] == -1:
            visit(u)
    return bridges, sorted(articulation)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap