fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3.  
  4. using namespace std;
  5.  
  6. using ll   = long long;
  7. using ii   = pair   < int , int >;
  8. using i3   = pair   < int , ii  >;
  9. using li   = pair   < ll  , int >;
  10. using lii  = pair   < ll  , ii  >;
  11. using pll  = pair   < ll  , ll  >;
  12. using vi   = vector < int       >;
  13. using vl   = vector < ll        >;
  14. using vii  = vector < ii        >;
  15. using vli  = vector < li        >;
  16. using vpll = vector < pll       >;
  17. using vi3  = vector < i3        >;
  18. using vlii = vector < lii       >;
  19.  
  20.  
  21. const int N = 4e5 + 5 , L = 20;
  22. const ll INF = 1e17 + 7;
  23. const double eps = 1e-9 , PI = acos(-1);
  24.  
  25.  
  26. int n , m , q;
  27.  
  28. vi adj[N] , Tree[N];
  29.  
  30. int low[N] , dfn[N] , timer = 0;
  31. int dep[N];
  32. int to [N][L];
  33. int sum[N][L];
  34. bool isCutPoint[N];
  35.  
  36. vii edgesStack;
  37. set < int > belong[N];
  38. int BCC[N];
  39. int bccCount = 0;
  40.  
  41. set < int > nodes;
  42.  
  43. int code  (int x){ return x + n + 1; }
  44. int decode(int x){ return x - n - 1; }
  45.  
  46. void processBlock(ii E){
  47.     if(edgesStack.empty()) return;
  48.  
  49.     bccCount ++;
  50.     while( !edgesStack.empty() ){
  51.             ii E2 = edgesStack.back(); edgesStack.pop_back();
  52.  
  53.             int u = E2.first;
  54.             int v = E2.second;
  55.  
  56.             belong[u].insert(bccCount);
  57.             belong[v].insert(bccCount);
  58.  
  59.             BCC[u] = bccCount;
  60.             BCC[v] = bccCount;
  61.  
  62.             if(E2 == E)break;
  63.     }
  64. }
  65.  
  66. void dfs(int u , int p){
  67.     dfn[u] = low[u] = ++ timer;
  68.     int retchel = 0;
  69.  
  70.     for(int v : adj[u]){
  71.             if(!dfn[v]){
  72.                     edgesStack.push_back({u , v});
  73.                     retchel ++;
  74.  
  75.                     dfs(v , u);
  76.  
  77.                     low[u] = min(low[u] , low[v]);
  78.  
  79.                     if((p == -1 && retchel > 1) || (p != -1 && dfn[u] <= low[v])){
  80.                             processBlock({u , v});
  81.                             isCutPoint[u] = 1;
  82.                     }
  83.             }
  84.             else if(v != p){
  85.                     low[u] = min(low[u] , dfn[v]);
  86.  
  87.                     if(dfn[v] < dfn[u]){
  88.                             edgesStack.push_back({u , v});
  89.                     }
  90.             }
  91.     }
  92. }
  93.  
  94. void buildBCCTree(){
  95.  
  96.     dfs(1 , 0);
  97.     processBlock({-1 , -1});
  98.  
  99.     for(int i = 1 ; i <= n ; i ++){
  100.  
  101.             if(isCutPoint[i]){
  102.  
  103.                     nodes.insert(i);
  104.                     for(int compNumber : belong[i]){
  105.                             int v = code(compNumber);
  106.  
  107.                             nodes.insert(v);
  108.  
  109.                             Tree[i].push_back(v);
  110.                             Tree[v].push_back(i);
  111.                     }
  112.             }
  113.     }
  114. }
  115.  
  116. void dfsTree(int u , int p){
  117.     to[u][0] = p;
  118.     sum[u][0] = (isCutPoint[u]);
  119.     dep[u] = 1 + dep[p];
  120.  
  121.     for(int v : Tree[u]){
  122.             if(v != p)dfsTree(v , u);
  123.     }
  124.  
  125. }
  126.  
  127. void traverseForest(){
  128.     dfsTree(*(nodes.begin()) , 0);
  129. }
  130.  
  131. void buildSparseTable(){
  132.     for(int j = 1 ; j < L ; j ++){
  133.             for(int u : nodes){
  134.                     to[u][j] =                 to[ to[u][j-1] ][j-1];
  135.                     sum[u][j] = sum[u][j-1] + sum[ to[u][j-1] ][j-1];
  136.             }
  137.     }
  138. }
  139.  
  140.  
  141. int getSum(int u , int v){
  142.     int ret = 0;
  143.     if(u == v) return 0;
  144.  
  145.     if(dep[u] < dep[v]) swap(u , v);
  146.  
  147.     int k = dep[u] - dep[v];
  148.  
  149.     for(int i = 0 ; i < L ; i ++){
  150.             if(k & (1 << i)){
  151.                     ret += sum[u][i];
  152.                     u = to[u][i];
  153.             }
  154.     }
  155.  
  156.     if(u == v)return ret + sum[u][0];
  157.  
  158.     for(int i = L-1 ; i >= 0 ; i --){
  159.             if(to[u][i] != to[v][i]){
  160.  
  161.                     ret += sum[u][i] + sum[v][i];
  162.  
  163.                     u = to[u][i];
  164.                     v = to[v][i];
  165.             }
  166.     }
  167.  
  168.     return ret + sum[u][0] + sum[v][0] + sum[ to[u][0] ][0];
  169. }
  170.  
  171. void solve(int testCase){
  172.  
  173.     scanf("%d %d" , &n , &m);
  174.  
  175.     for(int i = 0 ; i < m ; i ++){
  176.             int u , v; scanf("%d %d" , &u , &v);
  177.  
  178.             adj[u].push_back(v);
  179.             adj[v].push_back(u);
  180.     }
  181.  
  182.  
  183.     buildBCCTree();
  184.     traverseForest();
  185.     buildSparseTable();
  186.  
  187.     scanf("%d" , &q);
  188.  
  189.     while( q -- ){
  190.             int u , v; scanf("%d %d" , &u , &v);
  191.  
  192.             if(!isCutPoint[u])u = code(BCC[u]);
  193.             if(!isCutPoint[v])v = code(BCC[v]);
  194.  
  195.             int ans = getSum(u , v) - sum[u][0] - sum[v][0];
  196.             printf("%d\n" , max(0 , ans));
  197.     }
  198. }
  199.  
  200. main(){
  201.  
  202.     int t = 1;
  203.     // scanf("%d" , &t);
  204.  
  205.     for(int testCase = 1 ; testCase <= t ; testCase ++){
  206.             solve(testCase);
  207.     }
  208.  
  209.     return 0;
  210. }
Success #stdin #stdout 0.01s 41372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KlMt9E
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!