Dhiraj-01

articulation point

Sep 9th, 2021 (edited)
1,171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.65 KB | None | 0 0
  1. void dfs(ll u, ll p)
  2. {
  3.     vis[u] = 1;
  4.     lvl[u] = low[u] = 1 + lvl[p];
  5.     ll child = 0;
  6.     for(ll v : g[u])
  7.     {
  8.         if(v == p) continue;
  9.         if(!vis[v])
  10.         {
  11.             child++;
  12.             dfs(v, u);
  13.             if(u == 1) { // root case
  14.                 ap[u] = (ap[u] | child > 1);
  15.             }
  16.             else if(low[v] >= lvl[u]) {
  17.                 ap[u] = 1;
  18.             }
  19.             low[u] = min(low[u], low[v]);
  20.         }
  21.         else {
  22.             // back edge (u, v)
  23.             // update with lvl[v], not low[v] because we can use only 1 back edge
  24.             low[u] = min(low[u], lvl[v]);  
  25.         }
  26.     }
  27. }
Advertisement
Add Comment
Please, Sign In to add comment