Bridge edge in a graph

Problem Statement - link #

Given a Graph of V vertices and E edges and another edge(c - d), the task is to find if the given edge is a Bridge. i.e., removing the edge disconnects the graph.

Note: It is assumed that negative cost cycles do not exist in the input matrix.

Your Task: You don’t need to read input or print anything. Your task is to complete the function isBridge() which takes number of vertices V, the number of edges E, an adjacency list adj and two integers c and d denoting the edge as input parameters and returns 1 if the given edge c-d is a Bridge. Else, it returns 0.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:

c = 1, d = 2
Output:
1
Explanation:
From the graph, we can clearly see that
blocking the edge 1-2 will result in 
disconnection of the graph. So, it is 
a Bridge and thus the Output 1.

Constraints #

• 1 ≤ V,E ≤ 10^5
• 0 ≤ c, d ≤ V-1

Solutions #

class Solution
{
    public:
    bool vis[15000]={};
    void dfs(int node,vector<int> adj[]){
        vis[node] = 1;
        for(auto it : adj[node]){
            if(!vis[it])
            dfs(it,adj);
        }
    }
    //Function to find if the given edge is a bridge in graph.
    int isBridge(int V, vector<int> adj[], int c, int d) 
    {
        // Code here
       vector<int> temp[V];
       for(int i=0;i<V;i++){
           for(auto it : adj[i]){
               if((i==c && it==d) || (i==d && it==c))
               continue;
               temp[i].push_back(it);
           }
       }
       dfs(c,temp);
       return !vis[d];
    }
};