Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Bridges in a Graph

Hard · Graphs · Asked at Amazon, Google, Microsoft

A bridge is an edge whose removal increases the number of connected components. The undirected graph has no repeated edges. Print the number of bridges, then each bridge as u v with u < v, sorted by u then v.

Input

First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).

Output

The count, then the bridges (one per line).

Constraints

Tarjan: DFS assigning discovery times; low[v] = the earliest discovery time reachable from v's subtree using one back edge. Tree edge (u, v) is a bridge when low[v] > disc[u].

Example 1

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

2
3 4
4 5

Example 2

Input

3 3
1 2
2 3
3 1

Output

0

Hints

  1. Removing each edge and re-checking connectivity is O(m · (n + m)) — too slow.
  2. Tarjan: during DFS keep disc[v] (discovery time) and low[v] (smallest disc reachable from v's subtree with one back edge). A tree edge (u, v) is a bridge when low[v] > disc[u].

Approach

Run DFS from every unvisited node. When exploring tree edge u → v, after returning set low[u] = min(low[u], low[v]); for a back edge to an already-visited v (other than the edge we came from), set low[u] = min(low[u], disc[v]). If low[v] > disc[u], nothing in v's subtree can climb back to u or above without that edge, so it is a bridge. Skip the parent edge by its index, not the parent node. Sort the bridges for output; iterative DFS (or a bigger stack) handles deep graphs.

Complexity: O(n + m + b log b) time · O(n + m) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1); // (neighbour, edge id)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    vector<int> disc(n + 1, 0), low(n + 1, 0), parentEdge(n + 1, -1), it(n + 1, 0);
    vector<pair<int, int>> bridges;
    int timer = 0;
    for (int s = 1; s <= n; s++) {
        if (disc[s]) continue;
        stack<int> st;
        st.push(s);
        disc[s] = low[s] = ++timer;
        while (!st.empty()) {
            int u = st.top();
            if (it[u] < (int)adj[u].size()) {
                int v = adj[u][it[u]].first, id = adj[u][it[u]].second;
                it[u]++;
                if (id == parentEdge[u]) continue;
                if (disc[v]) low[u] = min(low[u], disc[v]);
                else {
                    parentEdge[v] = id;
                    disc[v] = low[v] = ++timer;
                    st.push(v);
                }
            } else {
                st.pop();
                if (!st.empty()) {
                    int p = st.top();
                    low[p] = min(low[p], low[u]);
                    if (low[u] > disc[p]) bridges.push_back({min(p, u), max(p, u)});
                }
            }
        }
    }
    sort(bridges.begin(), bridges.end());
    cout << bridges.size() << "\n";
    for (auto &b : bridges) cout << b.first << " " << b.second << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = data[2 + 2 * i], data[3 + 2 * i]
    adj[u].append((v, i))
    adj[v].append((u, i))
disc, low = [0] * (n + 1), [0] * (n + 1)
pedge, it = [-1] * (n + 1), [0] * (n + 1)
bridges, timer = [], 0
for s in range(1, n + 1):
    if disc[s]:
        continue
    timer += 1
    disc[s] = low[s] = timer
    stack = [s]
    while stack:
        u = stack[-1]
        if it[u] < len(adj[u]):
            v, eid = adj[u][it[u]]
            it[u] += 1
            if eid == pedge[u]:
                continue
            if disc[v]:
                low[u] = min(low[u], disc[v])
            else:
                pedge[v] = eid
                timer += 1
                disc[v] = low[v] = timer
                stack.append(v)
        else:
            stack.pop()
            if stack:
                p = stack[-1]
                low[p] = min(low[p], low[u])
                if low[u] > disc[p]:
                    bridges.append((min(p, u), max(p, u)))
bridges.sort()
print(len(bridges))
for a, b in bridges:
    print(a, b)

Java solution

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            in.nextToken();
            int u = (int) in.nval;
            in.nextToken();
            int v = (int) in.nval;
            adj.get(u).add(new int[] {v, i});
            adj.get(v).add(new int[] {u, i});
        }
        int[] disc = new int[n + 1], low = new int[n + 1], pedge = new int[n + 1], it = new int[n + 1], st = new int[n + 1];
        Arrays.fill(pedge, -1);
        List<int[]> bridges = new ArrayList<>();
        int timer = 0;
        for (int s = 1; s <= n; s++) {
            if (disc[s] != 0) continue;
            int top = 0;
            st[top++] = s;
            disc[s] = low[s] = ++timer;
            while (top > 0) {
                int u = st[top - 1];
                if (it[u] < adj.get(u).size()) {
                    int[] e = adj.get(u).get(it[u]++);
                    int v = e[0];
                    if (e[1] == pedge[u]) continue;
                    if (disc[v] != 0) low[u] = Math.min(low[u], disc[v]);
                    else {
                        pedge[v] = e[1];
                        disc[v] = low[v] = ++timer;
                        st[top++] = v;
                    }
                } else {
                    top--;
                    if (top > 0) {
                        int p = st[top - 1];
                        low[p] = Math.min(low[p], low[u]);
                        if (low[u] > disc[p]) bridges.add(new int[] {Math.min(p, u), Math.max(p, u)});
                    }
                }
            }
        }
        bridges.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        StringBuilder sb = new StringBuilder();
        sb.append(bridges.size()).append('\n');
        for (int[] b : bridges) sb.append(b[0]).append(' ').append(b[1]).append('\n');
        System.out.print(sb);
    }
}

Solve Bridges in a Graph online · All practice problems