at3107

articulation-point

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