Bridge edge in a graph

Given an undirected graph with V vertices numbered from 0 to V-1 and E edges, represented by 2d array edges[][], where edges[i]=[u,v] represents the edge between the vertices u and v. Determine whether a specific edge between two vertices (c, d) is a bridge.

Note:

• An edge is called a bridge if removing it increases the number of connected components of the graph.
• if there’s only one path between c and d (which is the edge itself), then that edge is a bridge.

Examples :

Input:

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:

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. All the Bridge Edges in the graph are marked with a blue line in the above image.

Constraints:
1 ≤ V, E ≤ 10⁵
0 ≤ c, d ≤ V-1

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    void dfs(int currentNode, vector<int> adjacencyList[], int source, int target, vector<int>& visited) {
        visited[currentNode] = true;

        for (int neighbor : adjacencyList[currentNode]) {
            if (!visited[neighbor] && !(currentNode == source && neighbor == target)) {
                dfs(neighbor, adjacencyList, source, target, visited);
            }
        }
    }

    bool isBridge(int vertexCount, vector<vector<int>>& edges, int source, int target) {
        vector<int> adjacencyList[vertexCount];

        for (const auto& edge : edges) {
            int nodeU = edge[0];
            int nodeV = edge[1];
            adjacencyList[nodeU].push_back(nodeV);
            adjacencyList[nodeV].push_back(nodeU);
        }

        vector<int> visited(vertexCount, 0);
        dfs(source, adjacencyList, source, target, visited);

        return !visited[target];
    }
};

from typing import List
from collections import defaultdict

class Solution:
    def dfs(self, currentNode: int, adjacencyList: List[List[int]], source: int, target: int, visited: List[bool]) -> None:
        visited[currentNode] = True

        for neighbor in adjacencyList[currentNode]:
            if not visited[neighbor] and not (currentNode == source and neighbor == target):
                self.dfs(neighbor, adjacencyList, source, target, visited)

    def isBridge(self, vertexCount: int, edges: List[List[int]], source: int, target: int) -> bool:
        adjacencyList = defaultdict(list)

        for nodeU, nodeV in edges:
            adjacencyList[nodeU].append(nodeV)
            adjacencyList[nodeV].append(nodeU)

        visited = [False] * vertexCount
        self.dfs(source, adjacencyList, source, target, visited)

        return not visited[target]

Time Complexity:

• Building the Graph:

  Inserting all edges into the adjacency list takes \( O(E) \) time, where \( E \) is the number of edges.

• DFS Traversal:

  The DFS may visit every vertex and edge once in the worst case, resulting in \( O(V + E) \) time.

• Total Time Complexity:

  \( O(V + E) \), where \( V \) is the number of vertices and \( E \) is the number of edges.

Space Complexity:

• Adjacency List:

  Stores all edges, taking \( O(V + E) \) space.

• Visited Array:

  A boolean array of size \( V \), resulting in \( O(V) \) space.

• Recursion Stack (DFS):

  In the worst case, DFS call stack can go as deep as \( O(V) \).

• Total Space Complexity:

  \( O(V + E) \)