Matrix_code

graph - Articulation point

Oct 8th, 2017 (edited)
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. // Articulation Point of a graph. O(V+E).
  2. int Time[N] , low[N];
  3. int dfn= 0;
  4. void dfs(int u,int p )
  5. {
  6.       Time[u] = low[u] = dfn ++;
  7.       vis[u]=1;
  8.       int cnt = 0;
  9.       for(auto a: G[u]) {
  10.             if(a==p) continue;
  11.             if(vis[a]) {
  12.                   low[u] = min(low[u] , Time[a]);
  13.             }
  14.             else {
  15.                   dfs(a,u);
  16.                   if(low[a] >= Time[u] ) {
  17.                         isAp[u]=1;
  18.                   }
  19.                   low[u] = min(low[u] , low[a]);
  20.                   cnt ++;
  21.             }
  22.       }
  23.       if(p==-1) {
  24.             isAp[u] = (cnt>1);
  25.       }
  26.      
  27. }
Add Comment
Please, Sign In to add comment