Advertisement
Riz1Ahmed

Articulation Points

Feb 20th, 2019
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. ///Given a graph. Count the Articulation points
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. int dis[110],point[110],c;//dis=vis
  5. vector<int> adj[110];
  6.  
  7. int ArtPoint(int p,int u){
  8.     if (dis[u]) return dis[u];
  9.     int mn=dis[u]=c++,i;
  10.     for (i=0; i<adj[u].size(); i++){
  11.         int v=adj[u][i];
  12.         if (v==p) continue;
  13.         if (dis[v]) {mn=min(mn,dis[v]);continue;}
  14.         int x=ArtPoint(u,v);
  15.         if (x>=dis[u]) point[u]++;
  16.         mn=min(mn,x);
  17.     }
  18.     return mn;
  19. }
  20. int main(){
  21.     int n,e,u,v,i,j,f;
  22.     for (i=0; i<110; i++) adj[i].clear();
  23.     memset(dis,0,sizeof dis),
  24.     memset(point,0,sizeof point);
  25.  
  26.     puts("Input how many node and edge:");
  27.     scanf("%d %d",&n,&e);
  28.  
  29.     puts("Input the edges one by one:");
  30.     for (i=0; i<e; i++){
  31.         scanf("%d %d",&u,&v);
  32.         adj[u].push_back(v);
  33.         adj[v].push_back(u);
  34.     }
  35.     for (i=c=1; i<=n; i++) ///Finding Articulation Point
  36.         if (!dis[i]){
  37.             dis[i]=c++;
  38.             for (j=f=0; j<adj[i].size(); j++)
  39.                 if (!dis[adj[i][j]])
  40.                     f++, ArtPoint(i,adj[i][j]);
  41.             if (f>1) point[i]=f;
  42.         }
  43.     puts("The Articulation poin(s) are:");
  44.     for (i=1; i<=n; i++) if (point[i]) printf("%d ",i);
  45.     return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement