Bridges in a Graph Using Tarjan's Algorithm

112.8k
0

Given a connected, undirected graph with V vertices numbered from 0 to V-1 and an edge list, return every bridge in the graph.

Deleting a bridge increases the number of connected components. Return every bridge as [minEndpoint, maxEndpoint] in lexicographically sorted order. Parallel edges are treated as separate edge occurrences.

Example 1

Input: V = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]

Output: [[1,3],[3,4]]

Explanation: Removing edge [1,3] separates vertices 3 and 4 from the cycle. Removing edge [3,4] isolates vertex 4.

Example 2

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0]]

Output: []

Explanation: Every edge belongs to a cycle, so removing any single edge preserves connectivity.

Brute Force Approach

Every edge can be removed temporarily, followed by a graph traversal from vertex 0. The original graph is connected, so DFS from vertex 0 reaches all V vertices before any removal. After removing one edge, a DFS count smaller than V proves that the removed edge was necessary for connectivity.

Using edge indices distinguishes parallel edge occurrences. Rebuilding adjacency while skipping one exact edge index preserves every remaining parallel connection.

Algorithm

  • Initialize an empty answer list for bridge pairs.

  • Iterate through every edge index, treating each edge occurrence as a bridge candidate.

  • Build an undirected adjacency list while skipping only the selected edge index.

  • Run DFS from vertex 0, using the connected-graph assumption to test complete reachability.

  • Count visited vertices and record the removed edge when the count is smaller than V.

  • Normalize every recorded bridge as [minEndpoint, maxEndpoint].

  • Sort the bridge list lexicographically and return the sorted result.

Dry Run

bridges in graph brute

bridges in graph brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts reachable vertices after skipping one edge.
int reachableCount(int vertices, vector<vector<int>>& edges, int skippedEdge) {
vector<vector<int>> adjacency(vertices);
// Build the graph without the selected edge occurrence.
for (int edgeId = 0; edgeId < static_cast<int>(edges.size()); edgeId++) {
// Skip only the current edge occurrence.
if (edgeId == skippedEdge) {
continue;
}
int first = edges[edgeId][0];
int second = edges[edgeId][1];
adjacency[first].push_back(second);
adjacency[second].push_back(first);
}
vector<bool> visited(vertices, false);
stack<int> pending;
// Start traversal from vertex zero.
pending.push(0);
visited[0] = true;
int reached = 0;
// Traverse the remaining graph from vertex zero.
while (!pending.empty()) {
int node = pending.top();
pending.pop();
// Count the current reachable vertex.
reached++;
// Visit all unvisited neighbors.
for (int neighbor : adjacency[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
pending.push(neighbor);
}
}
}
// Return total reachable vertices.
return reached;
}
public:
// Finds bridges by removing every edge once.
vector<vector<int>> findBridges(int vertices, vector<vector<int>>& edges) {
vector<vector<int>> bridges;
// Remove each edge occurrence and test graph connectivity.
for (int edgeId = 0; edgeId < static_cast<int>(edges.size()); edgeId++) {
// If fewer vertices are reachable, the edge is a bridge.
if (reachableCount(vertices, edges, edgeId) < vertices) {
int first = min(edges[edgeId][0], edges[edgeId][1]);
int second = max(edges[edgeId][0], edges[edgeId][1]);
bridges.push_back({first, second});
}
}
// Sort bridge endpoints for deterministic output.
sort(bridges.begin(), bridges.end());
return bridges;
}
};
// Driver code.
int main() {
int vertices = 5;
vector<vector<int>> edges = {
{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}
};
Solution solution;
vector<vector<int>> bridges = solution.findBridges(vertices, edges);
// Print every bridge edge.
for (const auto& edge : bridges) {
cout << "[" << edge[0] << "," << edge[1] << "] ";
}
return 0;
}

Complexity Analysis

Here, V is the number of vertices and E is the number of undirected edge occurrences.

Time Complexity: O(E×(V+E)), because every removed edge requires adjacency construction and DFS traversal.

Space Complexity: O(V+E), where rebuilt adjacency, visited markers, DFS storage, and the answer list store graph data.

Optimal Approach

Tarjan’s bridge algorithm uses one DFS to assign a discovery time to every vertex. A low-link value stores the smallest discovery time reachable through DFS tree edges followed by at most one back edge.

For a DFS tree edge from parent u to child v, condition low[v] > discovery[u] proves that the child subtree has no alternate route to u or an ancestor of u. Edge IDs distinguish parallel edge occurrences and prevent incorrect parent-edge skipping.

Algorithm

  • Build an undirected adjacency list containing {neighbor, edgeId} pairs, preserving every parallel edge occurrence.

  • Initialize discovery and low arrays with -1, then initialize the DFS timer.

  • Start DFS from vertex 0, since the problem guarantees a connected graph.

  • Skip only the exact parent edge ID during DFS, allowing parallel edges to update low-link values.

  • For every undiscovered neighbor v, run child DFS, update low[u] with low[v], and record a bridge when low[v] > discovery[u].

  • For every already discovered non-parent neighbor v, update low[u] with discovery[v], representing a back-edge connection.

  • Normalize every bridge endpoint pair, sort all bridges lexicographically, and return the final list.

Dry Run

bridges-iterative-dfs-restyled-correct

bridges-iterative-dfs-restyled-correct

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
struct Frame {
int node;
int parent;
int parentEdge;
int nextIndex;
};
public:
// Finds bridges using discovery and low-link times.
vector<vector<int>> findBridges(int vertices, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> adjacency(vertices);
// Store a unique id with every undirected edge occurrence.
for (int edgeId = 0; edgeId < static_cast<int>(edges.size()); edgeId++) {
int first = edges[edgeId][0];
int second = edges[edgeId][1];
adjacency[first].push_back({second, edgeId});
adjacency[second].push_back({first, edgeId});
}
vector<int> discovery(vertices, -1);
vector<int> low(vertices, -1);
vector<vector<int>> bridges;
int timer = 0;
// Start a DFS tree from every unvisited vertex.
for (int start = 0; start < vertices; start++) {
// Skip already discovered components.
if (discovery[start] != -1) {
continue;
}
stack<Frame> frames;
// Assign discovery and low time to the start vertex.
discovery[start] = low[start] = timer++;
frames.push({start, -1, -1, 0});
while (!frames.empty()) {
Frame& frame = frames.top();
int node = frame.node;
// Process the next adjacent edge from the current frame.
if (frame.nextIndex < static_cast<int>(adjacency[node].size())) {
auto [neighbor, edgeId] = adjacency[node][frame.nextIndex++];
// Skip only the exact edge used to enter the vertex.
if (edgeId == frame.parentEdge) {
continue;
}
// Tree edge: discover a new vertex.
if (discovery[neighbor] == -1) {
discovery[neighbor] = low[neighbor] = timer++;
frames.push({neighbor, node, edgeId, 0});
}
// Back edge: update low-link using discovery time.
else {
low[node] = min(low[node], discovery[neighbor]);
}
continue;
}
// Finish the vertex after all edges are processed.
Frame finished = frame;
frames.pop();
// Root has no parent to update.
if (finished.parent == -1) {
continue;
}
// Propagate low-link value upward.
low[finished.parent] = min(low[finished.parent], low[finished.node]);
// If child cannot reach parent or above, edge is a bridge.
if (low[finished.node] > discovery[finished.parent]) {
bridges.push_back({
min(finished.parent, finished.node),
max(finished.parent, finished.node)
});
}
}
}
// Sort bridge endpoints for deterministic output.
sort(bridges.begin(), bridges.end());
return bridges;
}
};
// Driver code.
int main() {
int vertices = 5;
vector<vector<int>> edges = {
{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}
};
Solution solution;
vector<vector<int>> bridges = solution.findBridges(vertices, edges);
// Print every bridge edge.
for (const auto& edge : bridges) {
cout << "[" << edge[0] << "," << edge[1] << "] ";
}
return 0;

Complexity Analysis

Here, V is the number of vertices and E is the number of undirected edge occurrences.

Time Complexity: O(V+E), because DFS processes every vertex and edge a constant number of times.

Space Complexity: O(V+E), where adjacency, discovery values, low-link values, DFS frames, edge IDs, and bridge pairs store graph state.

Interview follow-up Questions

Yes. An edge outside every cycle provides the only connection between both sides of the edge.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Given N cities numbered from 0 to N-1 , an array of bidirectional weighted roads [first, second, weight] , and a positive distanceThreshold , count the other cities reachable from every city with s...

105.7k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge app...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0