• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?