Check if removing a given edge disconnects a graph

Given a graph with V vertices and E edges, along with a specific edge connecting vertices c and d, the task is to determine whether this edge is a bridge. An edge (c–d) is said to be a bridge if removing it results in an increase in the number of connected components — meaning that vertices c and d were part of the same connected component before, but become disconnected after its removal.

Examples:

Input: V = 4, edges[][] = [[0, 1], [1, 2], [2, 3], [3, 4]]
c = 1, d = 2
Output: true
Explanation: From the graph, we can clearly see that blocking the edge 1-2 will result in disconnection of the graph.
Hence, it is a Bridge.

Input: V = 5, edges[][] = [[0, 1], [1, 2], [0, 2], [0, 3], [3, 4]]
c = 0, d = 2
Output: false
Explanation: Blocking the edge between nodes 0 and 2 won't affect the connectivity of the graph.
So, it's not a Bridge Edge.

The following are some example graphs with bridges highlighted in red.

Approach: Using DFS - O(V + E) Time and O(V) Space

The idea is to temporarily remove the edge (c, d) from the graph and check if it increases the number of connected components.
If removing the edge results in c and d no longer being connected — meaning there is no path between them — then the edge (c, d) is a bridge, as its removal disconnects the graph.
On the other hand, if c and d are still connected through other paths, then the edge is not a bridge.

Step by Step implementation:

• Remove the edge (c, d) from the graph.
• Check if nodes c and d are still connected.
  • If they are not connected, it means the edge (c, d) was the only path between them, so it's a bridge.
  • If they are still connected through other paths, then the edge is not a bridge.

#include <bits/stdc++.h> using namespace std; // dfs function to explore all reachable nodes void dfs(vector<vector<int>> &adj, int c, vector<bool> &visited) {  visited[c] = true;  for (auto i : adj[c]) {  if (!visited[i])  dfs(adj, i, visited);  } } // Construct adjacency list without the edge (c, d) vector<vector<int>> constructadj(int V,  vector<vector<int>> &edges, int c, int d) {  vector<vector<int>> adj(V);   for (auto &edge : edges) {    // Skip the edge (c, d) or (d, c)  if ((edge[0] == c && edge[1] == d) || (edge[0] == d && edge[1] == c))  continue;  adj[edge[0]].push_back(edge[1]);  adj[edge[1]].push_back(edge[0]);  }  return adj; } // Check if the edge (c, d) is a bridge bool isBridge(int V, vector<vector<int>> &edges, int c, int d) {  vector<vector<int>> adj = constructadj(V, edges, c, d);  vector<bool> visited(V, false);  dfs(adj, c, visited);    // if d is not reachable from c → bridge  return !visited[d];  } int main() {  int V = 4;  vector<vector<int>> edges = {{0, 1}, {1, 2}, {2,3}};  int c = 1, d = 2;  cout << (isBridge(V, edges, c, d) ? "true" : "false") << endl;  return 0; } 

import java.util.*; public class GfG {  // dfs function to visit nodes  static void dfs(List<Integer>[] adj, int c,  boolean[] visited) {  visited[c] = true;  for (int neighbor : adj[c]) {  if (!visited[neighbor]) {  dfs(adj, neighbor, visited);  }  }  }  // Build adjacency list from edge list, excluding edge  // (c, d)  static List<Integer>[] constructAdj(int V,  int[][] edges,  int c, int d) {  List<Integer>[] adj = new ArrayList[V];  for (int i = 0; i < V; i++)  adj[i] = new ArrayList<>();  for (int[] edge : edges) {  int a = edge[0], b = edge[1];  if ((a == c && b == d) || (a == d && b == c))  continue;  adj[a].add(b);  adj[b].add(a);  }  return adj;  }  static boolean isBridge(int V, int[][] edges, int c,  int d) {  List<Integer>[] adj = constructAdj(V, edges, c, d);  boolean[] visited = new boolean[V];  dfs(adj, c, visited);    // if d not reachable from c →  // edge (c, d) is a bridge  return !visited[d];   }  public static void main(String[] args)  {  int V = 4;  int[][] edges = {{ 0, 1 }, { 1, 2 }, { 2,3 }};  int c = 1, d = 2;  System.out.println(  isBridge(V, edges, c, d) ? "true" : "false");  } } 

def dfs(adj, c, visited): # Standard DFS traversal from node c visited[c] = True for neighbor in adj[c]: if not visited[neighbor]: dfs(adj, neighbor, visited) def constructadj(V, edges, c, d): # Build adjacency list, skipping the edge (c, d) adj = [[] for _ in range(V)] for a, b in edges: # Skip the edge we're testing as a potential bridge if (a == c and b == d) or (a == d and b == c): continue adj[a].append(b) adj[b].append(a) return adj def isBridge(V, edges, c, d): # Build the graph without edge (c, d) adj = constructadj(V, edges, c, d) visited = [False] * V # Run DFS starting from one end of the removed edge dfs(adj, c, visited) # If we can't reach the other node, it's a bridge return not visited[d] if __name__ == "__main__": # Number of vertices V = 4 # Edges of the graph edges = [[0, 1], [1, 2], [2, 3]] # Edge we want to test c, d = 1, 2 # Output true if the edge is a bridge, false otherwise print("true" if isBridge(V, edges, c, d) else "false") 

using System; using System.Collections.Generic; class GfG {  // Perform dfs from node 'd' and mark all reachable nodes  static void dfs(List<int>[] adj, int d, bool[] visited) {  visited[d] = true;  foreach (int neighbor in adj[d]) {  if (!visited[neighbor]) {  dfs(adj, neighbor, visited);  }  }  }  // Build adjacency list while skipping the edge (c, d)  static List<int>[] constructAdj(int V, int[,] edges, int c, int d) {  var adj = new List<int>[V];  // Initialize each adjacency list  for (int i = 0; i < V; i++) {  adj[i] = new List<int>();  }  // Get the number of edges  int E = edges.GetLength(0);  for (int i = 0; i < E; i++) {  int a = edges[i, 0];  int b = edges[i, 1];  // Skip the edge that we are testing for bridge  if ((a == c && b == d) || (a == d && b == c))  continue;  adj[a].Add(b);  adj[b].Add(a);  }  return adj;  }  // Check if edge (c, d) is a bridge  static bool isBridge(int V, int[,] edges, int c, int d) {  // Build the graph without the edge (c, d)  var adj = constructAdj(V, edges, c, d);  // Track visited nodes during DFS  bool[] visited = new bool[V];  // Start dfs from one end of the removed edge  dfs(adj, c, visited);  // If the other end is not reachable, it's a bridge  return !visited[d];  }  static void Main() {  // Number of vertices  int V = 4;  // Graph edges (undirected)  int[,] edges = {{ 0, 1 },{ 1, 2 },{ 2, 3 }};  // Edge to check if it’s a bridge  int c = 1, d = 2;  // Output whether the edge is a bridge  Console.WriteLine(isBridge(V, edges, c, d) ? "true" : "false");  } } 

// Perform DFS from node 'd' to mark all reachable nodes function dfs(adj, d, visited) {  visited[d] = true;  for (const neighbor of adj[d]) {  if (!visited[neighbor]) {  dfs(adj, neighbor, visited);  }  } } // Build the adjacency list while skipping the edge (c, d) function constructAdj(V, edges, c, d) {    // Create an empty adjacency list for each vertex  const adj = Array.from({ length: V }, () => []);  for (const [a, b] of edges) {  // Skip the edge we're testing for being a bridge  if ((a === c && b === d) || (a === d && b === c)) {  continue;  }  adj[a].push(b);  adj[b].push(a);  }  return adj; } // Check if the edge (c, d) is a bridge function isBridge(V, edges, c, d) {    // Construct the graph without the edge (c, d)  const adj = constructAdj(V, edges, c, d);  // Track visited nodes during DFS  const visited = new Array(V).fill(false);  // Start DFS from one end of the removed edge  dfs(adj, c, visited);  // If the other end is not reachable, it's a bridge  return !visited[d]; } // Number of vertices const V = 4; // Graph edges (undirected) const edges = [[0, 1],[1, 2],[2, 3]]; // Edge to test const c = 1, d = 2; // Output the result console.log(isBridge(V, edges, c, d) ? "true" : "false"); 

true 

Time Complexity: O(V + E) since DFS visits each vertex once O(V) and traverses all edges once O(E).
Auxiliary Space: O(V) for the visited array and recursive call stack (excluding adjacency list storage). We do not count the adjacency list in auxiliary space as it is necessary for representing the input graph.