Advertisement
mickypinata

SPOJ: LCA

Nov 7th, 2021
701
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1000;
  5. const int logN = log2(N);
  6.  
  7. vector<int> adj[N + 1];
  8. int rnk[N + 1], par[N + 1][logN + 1];
  9.  
  10. void DFS(int u, int p, int depth){
  11.     par[u][0] = p;
  12.     rnk[u] = depth;
  13.     for(int v : adj[u]){
  14.         if(v == p){
  15.             continue;
  16.         }
  17.         DFS(v, u, depth + 1);
  18.     }
  19. }
  20.  
  21. int main(){
  22.  
  23.     int T;
  24.     scanf("%d", &T);
  25.     for(int t = 1; t <= T; ++t){
  26.         cout << "Case " << t << ":\n";
  27.         int nVertex;
  28.         scanf("%d", &nVertex);
  29.         for(int u = 1; u <= nVertex; ++u){
  30.             adj[u].clear();
  31.         }
  32.         for(int u = 1; u <= nVertex; ++u){
  33.             int nEdge;
  34.             scanf("%d", &nEdge);
  35.             for(int i = 1; i <= nEdge; ++i){
  36.                 int v;
  37.                 scanf("%d", &v);
  38.                 adj[u].push_back(v);
  39.                 adj[v].push_back(u);
  40.             }
  41.         }
  42.         DFS(1, 0, 1);
  43.         for(int e = 1; e <= logN; ++e){
  44.             for(int u = 1; u <= nVertex; ++u){
  45.                 par[u][e] = par[par[u][e - 1]][e - 1];
  46.             }
  47.         }
  48.         int Q;
  49.         scanf("%d", &Q);
  50.         while(Q--){
  51.             int u, v;
  52.             scanf("%d%d", &u, &v);
  53.             if(rnk[u] < rnk[v]){
  54.                 swap(u, v);
  55.             }
  56.             for(int e = logN; e >= 0; --e){
  57.                 if(rnk[par[u][e]] >= rnk[v]){
  58.                     u = par[u][e];
  59.                 }
  60.             }
  61.             if(u == v){
  62.                 cout << u << '\n';
  63.                 continue;
  64.             }
  65.             for(int e = logN; e >= 0; --e)  {
  66.                 if(par[u][e] != par[v][e]){
  67.                     u = par[u][e];
  68.                     v = par[v][e];
  69.                 }
  70.             }
  71.             cout << par[u][0] << '\n';
  72.         }
  73.     }
  74.     return  0;
  75. }
  76.  
Advertisement
RAW Paste Data Copied
Advertisement