Log inSign up
hardGeeksforGeeksNot Started

Bridges in Graph

An edge in an undirected connected graph is a bridge if removing it disconnects the graph (increases the number of connected components). Find all bridges in the given graph.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an undirected graph with V vertices numbered 0 to V - 1 and a list of undirected edges.

A bridge (also known as a cut-edge) is an edge whose removal strictly increases the number of connected components in the graph.

Find all bridges in the graph. Return the list of bridges as pairs [u, v] (with u < v) in sorted order. If no bridge exists, return an empty list [].

---

### Examples

Example 1: ``text Input: V = 4, edges = [[0, 1], [1, 2], [2, 0], [1, 3]] Output: [[1, 3]] Explanation: Removing edge (1, 3) separates vertex 3 from the rest of the graph (components increase from 1 to 2). Edges (0, 1), (1, 2), and (2, 0) form a cycle; removing any one of them leaves the other vertices connected.

Example 2: ``text Input: V = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]] Output: [[0, 1], [1, 2], [2, 3], [3, 4]] Explanation: The graph is a simple line graph. Every single edge is a bridge!

---

### Constraints - 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - Graph may contain multiple disconnected components. - No self-loops or parallel edges.

Constraints:

  • 1 <= V <= 105
  • 0 <= edges.length <= 105
  • 0 <= u, v < V
  • Graph may be disconnected

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate between Articulation Points (cut vertices) and Bridges (cut edges).
  • Master low-link values (low[u]) and discovery times (tin[u]) in DFS trees.
  • Identify the exact condition low[v] > tin[u] for bridges.
  • Implement the complete bridge-finding algorithm in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Identifying critical network links whose failure isolates components.
  • Finding critical edges or minimum cuts in communication networks.
  • Graph decomposition into 2-edge-connected components.

Algorithmic Decision Tree:

  • BRUTE FORCE: Remove each edge one-by-one and run BFS/DFS -> O(E * (V + E)) - too slow for V, E = 105.
  • OPTIMAL: Tarjan's DFS bridge algorithm -> O(V + E) single pass.

Connected Patterns:

Critical Connections in a Network (LeetCode 1192)Articulation PointsTarjan's Strongly Connected Components

1. Edge-by-Edge Removal Connectivity Test

Intuition

Remove each edge one by one. Run BFS/DFS to count connected components. If components increase, the removed edge is a bridge.

Algorithm

  1. Count baseline connected components of original graph using BFS/DFS.
  2. For each edge (u, v) in the edge list:
  3. Remove (u, v) from the adjacency list.
  4. Run BFS/DFS to count new connected components.
  5. If new count > baseline count, record (u, v) as a bridge.
  6. Re-insert (u, v) back into the adjacency list.
  7. Return all recorded bridges.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited, pair<int, int> skipEdge) {
8 visited[u] = true;
9 for (int v : adj[u]) {
10 if ((u == skipEdge.first && v == skipEdge.second) || (u == skipEdge.second && v == skipEdge.first)) {
11 continue; // Skip the candidate bridge edge
12 }
13 if (!visited[v]) {
14 dfs(v, adj, visited, skipEdge);
15 }
16 }
17}
18
19int countComponents(int V, const vector<vector<int>>& adj, pair<int, int> skipEdge = {-1, -1}) {
20 vector<bool> visited(V, false);
21 int count = 0;
22 for (int i = 0; i < V; ++i) {
23 if (!visited[i]) {
24 count++;
25 dfs(i, adj, visited, skipEdge);
26 }
27 }
28 return count;
29}
30
31vector<vector<int>> findBridgesBruteForce(int V, const vector<vector<int>>& edges) {
32 vector<vector<int>> adj(V);
33 for (const auto& e : edges) {
34 adj[e[0]].push_back(e[1]);
35 adj[e[1]].push_back(e[0]);
36 }
37
38 int baseComponents = countComponents(V, adj);
39 vector<vector<int>> bridges;
40
41 for (const auto& e : edges) {
42 int u = e[0], v = e[1];
43 int newComponents = countComponents(V, adj, {u, v});
44 if (newComponents > baseComponents) {
45 bridges.push_back({min(u, v), max(u, v)});
46 }
47 }
48 return bridges;
49}
50
51int main() {
52 int V = 4;
53 vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}};
54 auto bridges = findBridgesBruteForce(V, edges);
55 cout << "Bridges found: ";
56 for (const auto& b : bridges) cout << "[" << b[0] << ", " << b[1] << "] ";
57 cout << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(E * (V + E))
  • Space complexity: O(V + E)

2. 2-Pass Spanning Tree Cycle Classification

Intuition

Build a DFS spanning tree. Back-edges identify cycles. Mark all tree edges that are covered by at least one back-edge cycle. Unmarked tree edges are bridges.

Algorithm

  1. Construct a DFS tree, partitioning edges into Tree Edges and Back Edges.
  2. Each back-edge creates a fundamental cycle on tree edges between the two endpoints.
  3. Propagate cycle coverage tags up the DFS tree using a prefix-sum / difference array technique.
  4. Tree edges with 0 covering cycles are bridges.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7// Two-pass cycle counting via tree prefix difference
8void dfsTree(int u, int p, const vector<vector<int>>& adj, vector<int>& depth, vector<int>& cycleDiff, vector<pair<int, int>>& treeEdges) {
9 for (int v : adj[u]) {
10 if (v == p) continue;
11 if (depth[v] != -1) {
12 // Back-edge
13 if (depth[v] < depth[u]) {
14 cycleDiff[u]++;
15 cycleDiff[v]--;
16 }
17 } else {
18 depth[v] = depth[u] + 1;
19 treeEdges.push_back({u, v});
20 dfsTree(v, u, adj, depth, cycleDiff, treeEdges);
21 }
22 }
23}
24
25int dfsAccumulate(int u, int p, const vector<vector<int>>& adj, vector<int>& cycleDiff, const vector<int>& depth, vector<vector<int>>& bridges) {
26 int sum = cycleDiff[u];
27 for (int v : adj[u]) {
28 if (v != p && depth[v] == depth[u] + 1) {
29 int childSum = dfsAccumulate(v, u, adj, cycleDiff, depth, bridges);
30 if (childSum == 0) {
31 bridges.push_back({min(u, v), max(u, v)});
32 }
33 sum += childSum;
34 }
35 }
36 return sum;
37}
38
39int main() {
40 int V = 4;
41 vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}};
42 vector<vector<int>> adj(V);
43 for (const auto& e : edges) {
44 adj[e[0]].push_back(e[1]);
45 adj[e[1]].push_back(e[0]);
46 }
47
48 vector<int> depth(V, -1);
49 vector<int> cycleDiff(V, 0);
50 vector<pair<int, int>> treeEdges;
51
52 depth[0] = 0;
53 dfsTree(0, -1, adj, depth, cycleDiff, treeEdges);
54
55 vector<vector<int>> bridges;
56 dfsAccumulate(0, -1, adj, cycleDiff, depth, bridges);
57
58 cout << "Bridges via cycle tagging: ";
59 for (auto& b : bridges) cout << "[" << b[0] << ", " << b[1] << "] ";
60 cout << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

3. Tarjan's Bridge-Finding Algorithm (Discovery & Low-Link)

Intuition

Execute a single DFS traversal maintaining discovery timestamps tin[u] and lowest ancestor reach low[u]. A tree edge (u, v) is a bridge if low[v] > tin[u].

Algorithm

  1. Initialize timer = 0, tin and low arrays filled with -1, and visited array.
  2. For each vertex i from 0 to V - 1, if unvisited, call dfs(i, -1).
  3. In dfs(u, p):
  4. Mark visited[u] = true, set tin[u] = low[u] = ++timer.
  5. For each neighbor v of u:
  6. If v == p, continue (do not traverse bidirectional edge backwards).
  7. If visited[v] is true:
  8. Update low[u] = min(low[u], tin[v]) (back-edge found).
  9. If visited[v] is false:
  10. Recurse dfs(v, u).
  11. Update low[u] = min(low[u], low[v]) on return.
  12. If low[v] > tin[u], then edge [min(u, v), max(u, v)] is a bridge!
  13. Return the collection of bridges sorted.

Tarjan's DFS Bridge Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Visit 0: tin[0] = low[0] = 1
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Explore neighbor 1
Why this step matters

Visit 0: tin[0] = low[0] = 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int timer = 0;
9
10 void dfs(int u, int p, const vector<vector<int>>& adj, vector<int>& tin, vector<int>& low, vector<bool>& visited, vector<vector<int>>& bridges) {
11 visited[u] = true;
12 tin[u] = low[u] = ++timer;
13
14 for (int v : adj[u]) {
15 if (v == p) continue; // Skip parent edge
16
17 if (visited[v]) {
18 // Back-edge
19 low[u] = min(low[u], tin[v]);
20 } else {
21 // Forward tree edge
22 dfs(v, u, adj, tin, low, visited, bridges);
23 low[u] = min(low[u], low[v]);
24
25 // Bridge condition
26 if (low[v] > tin[u]) {
27 bridges.push_back({min(u, v), max(u, v)});
28 }
29 }
30 }
31 }
32
33public:
34 vector<vector<int>> findBridges(int V, const vector<vector<int>>& edges) {
35 vector<vector<int>> adj(V);
36 for (const auto& e : edges) {
37 adj[e[0]].push_back(e[1]);
38 adj[e[1]].push_back(e[0]);
39 }
40
41 vector<int> tin(V, -1);
42 vector<int> low(V, -1);
43 vector<bool> visited(V, false);
44 vector<vector<int>> bridges;
45 timer = 0;
46
47 for (int i = 0; i < V; ++i) {
48 if (!visited[i]) {
49 dfs(i, -1, adj, tin, low, visited, bridges);
50 }
51 }
52
53 sort(bridges.begin(), bridges.end());
54 return bridges;
55 }
56};
57
58int main() {
59 int V = 4;
60 vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}};
61 Solution solver;
62 auto bridges = solver.findBridges(V, edges);
63 cout << "Optimal Tarjan Bridges: ";
64 for (const auto& b : bridges) {
65 cout << "[" << b[0] << ", " << b[1] << "] ";
66 }
67 cout << endl;
68 return 0;
69}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Remove each edge & test connectivity)O(E * (V + E))O(V + E)Iterate through every edge, temporarily delete it, run BFS/DFS to count connected components.Re-running full graph traversal for every single edge.
2.Spanning Forest Cycle TaggingO(V + E)O(V + E)Construct a DFS spanning forest and mark all cycle-covered edges.Managing tree path mark arrays.
3.Tarjan's DFS Low-Link Algorithm (Optimal)OptimalO(V + E)O(V + E)Single DFS traversal computing discovery time tin and lowest reachable ancestor time low. Edge (u, v) is a bridge if low[v] > tin[u].Standard DFS tree traversal.

Common Pitfalls & Crucial Edge Cases

Not skipping immediate parent in DFS

Treating the parent edge as a back-edge erroneously suppresses all bridge detections.

Using >= instead of >

Confusing the bridge condition low[v] > tin[u] with the articulation point condition low[v] >= tin[u].

Failing to handle disconnected components

Missing the outer loop for (int i = 0; i < V; ++i).

Crucial Edge Cases to Validate:

  • Complete Graph K_n (n >= 3) — Every edge is part of multiple triangles/cycles; returns [] (0 bridges).
  • Tree Graph with V vertices — Every single edge in a tree is a bridge; returns all V - 1 edges.
  • Disconnected Graph — Outer loop must iterate across all unvisited vertices 0 to V - 1 to handle every component.
  • Graph with 0 or 1 edge — Edge is a bridge if V >= 2.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by clearly defining: an edge is a bridge if and only if it does not belong to any cycle.
  2. Explain low-link values using discovery time timestamps.
  3. Mention that LeetCode 1192 (Critical Connections in a Network) is the exact same problem.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the condition for a bridge low[v] > tin[u] strictly greater, whereas for an articulation point it is low[v] >= tin[u]?

2.Why must we skip the edge back to the direct parent (if (neighbor == parent) continue) during DFS traversal?

Back to DSA Sheet