Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.6 kB
0
Indexable
Never
//undirected unweighted graph
#include<vector>
#include<unordered_map>
#include<list>
void dfs(int node,int parent,int&timer,vector<int>&disc,vector<int>&low,vector<vector<int>>&result,unordered_map<int, list<int>>&adj,unordered_map<int,bool>&vis){  //node,disc,low,timer,adj
    vis[node]=true;
    disc[node]=low[node]=timer++;

    for(auto nbr:adj[node]){
        if(nbr==parent) continue;
        if(!vis[nbr]){
            dfs(nbr,node,timer,disc,low,result,adj,vis);

            low[node]=min(low[node],low[nbr]); //after dfs .. child may have lessser lowest  time
            
            if(low[nbr] > disc[node]){ //this is a bridge ..nbr has to go thru node so bridge between node and nbr
                vector<int> ans;
                ans.push_back(node);
                ans.push_back(nbr);
                result.push_back(ans);
            }
        }else{ //backedge

            low[node]=min(low[node],disc[nbr]); //other backedges present 
        }
    }

}
vector<vector<int>> findBridges(vector<vector<int>> &edges, int v, int e) {

    unordered_map<int, list<int>> adj;
    for(int i=0;i<edges.size();i++){
        int u=edges[i][0];
        int v=edges[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    //DS
    int parent=-1;
    int timer=0;
    vector<int>disc(v,-1);
    vector<int>low(v,-1);
    unordered_map<int,bool> vis;

    vector<vector<int>> result;
    for(int i=0;i<v;i++){
        if(!vis[i]){
            dfs(i,parent,timer,disc,low,result,adj,vis);
        }
    }
    return result;
}