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
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2 · 10^5
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
- Removing each edge and re-checking connectivity is O(m · (n + m)) — too slow.
- 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);
}
}