Guest User

Bridges

a guest
Jul 8th, 2020
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<set>
  5. #include<iterator>
  6. #include<math.h>
  7. #include<queue>
  8. #include<stack>
  9. using namespace std;
  10. #define SIZE 100001
  11.  
  12. vector<int>adj[SIZE];
  13. bool visited[SIZE];
  14. int parent[SIZE];
  15. int in_time[SIZE];
  16. int low[SIZE];
  17.  
  18. int timer =0;
  19.  
  20. void dfs_Bridge(int u ){
  21.    
  22.     visited[u]=1;
  23.     in_time[u]=timer;
  24.     low[u]=timer;
  25.     timer++;
  26.    
  27.     for(int child : adj[u]){
  28.        
  29.         if(visited[child]==0){
  30.             parent[child] = u;         
  31.             dfs_Bridge(child);
  32.             low[u]=min(low[child],low[u]);
  33.            
  34.             if(low[child]>in_time[u])
  35.             cout<<child<<" --> "<<u<<"\n";
  36.         }
  37.         else if(parent[u]!=child){
  38.             low[u]=min(low[child],in_time[u]);
  39.         }
  40.     }
  41. }
  42.  
  43. int main()
  44. {
  45.     int N,M;
  46.     cin>>N>>M;
  47.      
  48.     int i,x,y;
  49.      
  50.     for(i=1;i<=N;i++){
  51.         visited[i]=0;
  52.         parent[i]=-1;
  53.         low[i]=INT32_MAX;
  54.     }
  55.    
  56.     for(i=0;i<M;i++){
  57.         cin>>x>>y;
  58.         adj[x].push_back(y);
  59.         adj[y].push_back(x);
  60.     }
  61.    
  62.    
  63.    
  64.     int s=1;
  65.     dfs_Bridge(s);
  66.    
  67.     return 0;
  68. }
  69.  
  70. /*
  71. 4 6
  72. 1 3
  73. 1 4
  74. 2 1
  75. 3 2
  76. 4 2
  77. 4 3
  78. */
Add Comment
Please, Sign In to add comment