fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define maxn 200005
  5. #define LOG 20
  6.  
  7. int n,m,q;
  8. vector<pair<int,int>> g[maxn];
  9.  
  10. int U[maxn], V[maxn];
  11.  
  12. // Tarjan
  13. int dfn[maxn], low[maxn], timer;
  14. bool isBridge[maxn];
  15. vector<int> st;
  16.  
  17. // block-cut tree
  18. vector<int> bc[maxn*2];
  19. int id; // total node in bc tree
  20.  
  21. // mark visited in bcc
  22. int seen[maxn], stamp;
  23.  
  24. // ---------- Tarjan DFS ----------
  25. void dfs(int u, int pEdge){
  26.     dfn[u] = low[u] = ++timer;
  27.  
  28.     for(auto [v, idEdge] : g[u]){
  29.         if(idEdge == pEdge) continue;
  30.  
  31.         if(!dfn[v]){
  32.             st.push_back(idEdge);
  33.             dfs(v, idEdge);
  34.             low[u] = min(low[u], low[v]);
  35.  
  36.             // bridge
  37.             if(low[v] > dfn[u]) isBridge[idEdge] = 1;
  38.  
  39.             // build bcc
  40.             if(low[v] >= dfn[u]){
  41.                 int node = ++id;
  42.  
  43.                 stamp++;
  44.                 while(true){
  45.                     int e = st.back(); st.pop_back();
  46.                     int a = U[e], b = V[e];
  47.  
  48.                     if(seen[a] != stamp){
  49.                         seen[a] = stamp;
  50.                         bc[a].push_back(node);
  51.                         bc[node].push_back(a);
  52.                     }
  53.                     if(seen[b] != stamp){
  54.                         seen[b] = stamp;
  55.                         bc[b].push_back(node);
  56.                         bc[node].push_back(b);
  57.                     }
  58.  
  59.                     if(e == idEdge) break;
  60.                 }
  61.             }
  62.         }
  63.         else if(dfn[v] < dfn[u]){
  64.             st.push_back(idEdge);
  65.             low[u] = min(low[u], dfn[v]);
  66.         }
  67.     }
  68. }
  69.  
  70. // ---------- LCA ----------
  71. int up[maxn*2][LOG], depth[maxn*2], val[maxn*2];
  72.  
  73. void dfs_lca(int u, int p){
  74.     for(int v: bc[u]){
  75.         if(v == p) continue;
  76.         depth[v] = depth[u] + 1;
  77.         up[v][0] = u;
  78.         val[v] += val[u];
  79.         dfs_lca(v,u);
  80.     }
  81. }
  82.  
  83. int lca(int u, int v){
  84.     if(depth[u] < depth[v]) swap(u,v);
  85.  
  86.     int k = depth[u] - depth[v];
  87.     for(int i=0;i<LOG;i++)
  88.         if(k>>i&1) u = up[u][i];
  89.  
  90.     if(u==v) return u;
  91.  
  92.     for(int i=LOG-1;i>=0;i--){
  93.         if(up[u][i] != up[v][i]){
  94.             u = up[u][i];
  95.             v = up[v][i];
  96.         }
  97.     }
  98.     return up[u][0];
  99. }
  100.  
  101. // ---------- DSU for bridge tree ----------
  102. int par[maxn];
  103.  
  104. int find(int u){
  105.     return par[u]==u ? u : par[u]=find(par[u]);
  106. }
  107.  
  108. void unite(int u,int v){
  109.     u=find(u); v=find(v);
  110.     if(u!=v) par[v]=u;
  111. }
  112.  
  113. vector<int> tree[maxn];
  114. int dep2[maxn], up2[maxn][LOG];
  115.  
  116. void dfs2(int u, int p){
  117.     for(int v: tree[u]){
  118.         if(v==p) continue;
  119.         dep2[v] = dep2[u] + 1;
  120.         up2[v][0] = u;
  121.         dfs2(v,u);
  122.     }
  123. }
  124.  
  125. int lca2(int u,int v){
  126.     if(dep2[u] < dep2[v]) swap(u,v);
  127.  
  128.     int k = dep2[u]-dep2[v];
  129.     for(int i=0;i<LOG;i++)
  130.         if(k>>i&1) u=up2[u][i];
  131.  
  132.     if(u==v) return u;
  133.  
  134.     for(int i=LOG-1;i>=0;i--){
  135.         if(up2[u][i]!=up2[v][i]){
  136.             u=up2[u][i];
  137.             v=up2[v][i];
  138.         }
  139.     }
  140.     return up2[u][0];
  141. }
  142.  
  143. // ---------- MAIN ----------
  144. int main(){
  145.     ios::sync_with_stdio(0); cin.tie(0);
  146.  
  147.     cin>>n>>m>>q;
  148.  
  149.     for(int i=1;i<=m;i++){
  150.         cin>>U[i]>>V[i];
  151.         g[U[i]].push_back({V[i],i});
  152.         g[V[i]].push_back({U[i],i});
  153.     }
  154.  
  155.     id = n;
  156.  
  157.     dfs(1,0);
  158.  
  159.     // ----- prepare block-cut tree -----
  160.     for(int i=1;i<=n;i++) val[i]=1; // chỉ tính node gốc
  161.  
  162.     dfs_lca(1,0);
  163.  
  164.     for(int j=1;j<LOG;j++)
  165.         for(int i=1;i<=id;i++)
  166.             up[i][j]=up[ up[i][j-1] ][j-1];
  167.  
  168.     // ----- build bridge tree -----
  169.     for(int i=1;i<=n;i++) par[i]=i;
  170.  
  171.     for(int i=1;i<=m;i++){
  172.         if(!isBridge[i])
  173.             unite(U[i],V[i]);
  174.     }
  175.  
  176.     map<int,int> mp;
  177.     int cnt=0;
  178.  
  179.     for(int i=1;i<=n;i++){
  180.         int r = find(i);
  181.         if(!mp[r]) mp[r]=++cnt;
  182.     }
  183.  
  184.     for(int i=1;i<=m;i++){
  185.         if(isBridge[i]){
  186.             int a = mp[find(U[i])];
  187.             int b = mp[find(V[i])];
  188.             tree[a].push_back(b);
  189.             tree[b].push_back(a);
  190.         }
  191.     }
  192.  
  193.     dfs2(1,0);
  194.  
  195.     for(int j=1;j<LOG;j++)
  196.         for(int i=1;i<=cnt;i++)
  197.             up2[i][j]=up2[ up2[i][j-1] ][j-1];
  198.  
  199.     // ----- queries -----
  200.     while(q--){
  201.         int s,t;
  202.         cin>>s>>t;
  203.  
  204.         // vertex
  205.         int L = lca(s,t);
  206.         int ansV = val[s] + val[t] - 2*val[L] + 1;
  207.  
  208.         // edge
  209.         int a = mp[find(s)];
  210.         int b = mp[find(t)];
  211.         int L2 = lca2(a,b);
  212.         int ansE = dep2[a] + dep2[b] - 2*dep2[L2];
  213.  
  214.         cout<<ansV<<" "<<ansE<<"\n";
  215.     }
  216. }
Success #stdin #stdout 0.01s 27988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oYKz8V
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!