at3107

articulation bridge

Oct 30th, 2020
572
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define F first
  4. #define S second
  5. int tim=0;
  6. vector<bool> vis;
  7. vector<int> tin,low;
  8. set<pair<int,int> > ans;
  9. vector<int> adj[100005];
  10. void dfs(int v,int p)
  11. {
  12.     low[v]=tin[v]=tim++;
  13.     vis[v]=1;
  14.     for(auto u:adj[v])
  15.     {
  16.         if(u==p) continue;
  17.         if(vis[u]) low[v]=min(low[v],tin[u]);
  18.         else
  19.         {
  20.             dfs(u,v);
  21.             low[v]=min(low[v],low[u]);
  22.             if(low[u]>tin[v]) ans.insert({min(u,v),max(u,v)});
  23.         }
  24.     }
  25. }
  26. int main()
  27. {
  28.     int n,m;
  29.     cin>>n>>m;
  30.     for(int i=0;i<m;i++)
  31.     {
  32.         int a,b;
  33.         cin>>a>>b;
  34.         adj[a].push_back(b);
  35.         adj[b].push_back(a);
  36.     }
  37.     vis.assign(n+1,0);
  38.     tin.assign(n+1,-1);
  39.     low.assign(n+1,-1);
  40.     for(int i=0;i<n;i++)
  41.     {
  42.         if(!vis[i]) dfs(i,-1);
  43.     }
  44.     for(auto i:ans) cout<<i.F<<' '<<i.S<<endl;
  45.     return 0;
  46. }
RAW Paste Data