Advertisement
istinishat

Articulation Point

Feb 25th, 2017
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<vector>
  5. using namespace std;
  6.  
  7. #define si(n) scanf("%d",&n)
  8. #define MAX 10005
  9.  
  10. vector<int>graph[MAX];
  11. bool vis[MAX],arti_point[MAX];
  12. int time,disc[MAX],low[MAX];
  13.  
  14. void dfs(int now,int prev){
  15.     vis[now]=true;
  16.     disc[now]=low[now]=time++;
  17.     int child=0;
  18.     for(int i=0;i<graph[now].size();i++){
  19.         int to=graph[now][i];
  20.         if(to==prev)
  21.             continue;
  22.         if(vis[to])
  23.             low[now]=min(low[now],disc[to]);
  24.         else{
  25.             dfs(to,now);
  26.             low[now]=min(low[now],low[to]);
  27.             if(low[to]>=disc[now] && prev != -1){
  28.                 //now is articulation point
  29.                 arti_point[now]=true;
  30.             }
  31.             child++;
  32.         }
  33.     }
  34.     if(prev == -1 && child>1){
  35.         //now is articulation point
  36.         arti_point[now]=true;
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     int i,j,n,m;
  43.     freopen("input.txt","r",stdin);
  44.     si(n);si(m);
  45.     for(i=0;i<m;i++){
  46.         int u,v;
  47.         si(u);si(v);
  48.         graph[u].push_back(v);
  49.         graph[v].push_back(u);
  50.     }
  51.     memset(arti_point,false,sizeof(arti_point));
  52.     memset(vis,false,sizeof(vis));
  53.  
  54.     for(i=0;i<n;i++){
  55.         if(!vis[i])
  56.             dfs(i,-1);
  57.     }
  58.     int ans=0;
  59.     for(i=0;i<=n;i++)
  60.         if(arti_point[i])
  61.             ans++,cout<<i<<' ';
  62.     cout<<endl;
  63.     cout<<ans<<endl;
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement