Untitled
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; }