SHARE
TWEET

Finding LCA

RaFiN_ Jun 29th, 2020 777 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. // Caution : must b 0 based node ....
  4. void dfs(int v, int pr){
  5.     tin[v] = T++;
  6.     p[0][v] = pr;
  7.     u[v] = true;
  8.     for(int i = 1; i < LOGN; ++i)
  9.         p[i][v] = p[i - 1][ p[i - 1][v] ];
  10.        
  11.     for(auto e : g[v]){
  12.         int to = e.first, len = e.second;
  13.         if(!u[to]){
  14.             dfs(to, v);    
  15.         }
  16.     }  
  17.        
  18.     tout[v] = T;
  19. }
  20.  
  21. bool isAncestor(int a, int b){
  22.     return tin[a] <= tin[b] && tout[a] >= tout[b];
  23. }
  24.  
  25. int getLCA(int a, int b){
  26.     if(isAncestor(a, b)) return a;
  27.     if(isAncestor(b, a)) return b;
  28.    
  29.     for(int i = LOGN - 1; i >= 0; --i)
  30.         if(!isAncestor(p[i][a], b))
  31.             a = p[i][a];
  32.    
  33.     return p[0][a];
  34. }
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
Top