| 495 | } |
| 496 | |
| 497 | void bridgeInGraph(int node,int parent,int& timer,vector<int>&vis,vector<int>&low,vector<int>&in,vector<int>arr[]){ |
| 498 | vis[node]=1; |
| 499 | low[node]=in[node]=timer; |
| 500 | timer++; |
| 501 | |
| 502 | for(auto it : arr[node]){ |
| 503 | if(it==parent)continue; |
| 504 | if(vis[it]==1){ |
| 505 | low[node]=min(low[node],in[it]); |
| 506 | }else{ |
| 507 | bridgeInGraph(it,node,timer,vis,low,in,arr); |
| 508 | //after dfs call we backtrack |
| 509 | //if in[node] value is smaller than low[it] then it is an bridge edge. |
| 510 | //how? because if in[node] is smaller than it means that "it" is not |
| 511 | //connect to any ansistor and does not have any other path to reach. |
| 512 | //if if[node] is greater that means "it" is connect to the ansistor so it has more paths to reach it. |
| 513 | if(in[node]<low[it]){ |
| 514 | cout<<node<<" - "<<it<<" is a bridge"; |
| 515 | } |
| 516 | } |
| 517 | } |
| 518 | } |
| 519 | |
| 520 | //shortest path in a graph with -ve weights |
| 521 | void bellmenFord(int source){ |
nothing calls this directly
no outgoing calls
no test coverage detected