SHARE
TWEET

Untitled

a guest Nov 18th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define Edge pair<int,int>
  2. #define ff first
  3. #define ss second
  4. int cnt = 0,bcc_cnt = 0;
  5. vector<int> G[MAXN],bcc[MAXN];
  6. int pre[MAXN],low[MAXN],iscut[MAXN],bccno[MAXN];
  7. stack<Edge> S;
  8. void DFS(int u,int p)
  9. {
  10.     low[u] = pre[u] = ++cnt;
  11.     int child = 0;
  12.     for(auto v : G[u])
  13.     {
  14.         Edge e = {u,v};
  15.         if(!pre[v])
  16.         {
  17.             S.push(e);
  18.             child ++;
  19.             DFS(v,u);
  20.             low[u] = min(low[u],low[v]);
  21.             if(low[v] >= pre[u])
  22.             {
  23.                 iscut[u] = 1;
  24.                 bcc_cnt++;
  25.                 while(1)
  26.                 {
  27.                     Edge x = S.top();S.pop();
  28.                     if(bccno[x.ff] != bcc_cnt)
  29.                     {
  30.                       bccno[x.ff] = bcc_cnt;
  31.                       bcc[bcc_cnt].push_back(x.ff);
  32.                     }
  33.                     if(bccno[x.ss] != bcc_cnt)
  34.                     {
  35.                       bccno[x.ss] = bcc_cnt;
  36.                       bcc[bcc_cnt].push_back(x.ss);
  37.                     }
  38.                     if(x.ff == u && x.ss == v) break;
  39.                 }
  40.             }
  41.         }
  42.         else if(pre[v] < pre[u] && v != p)
  43.         {
  44.             S.push(e);
  45.             low[u] = min(low[u],pre[v]);
  46.         }
  47.     }
  48.     if(p <= 0 && child == 1)
  49.     {
  50.         iscut[u] = 0;
  51.     }
  52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top