matbensch

Untitled

Mar 5th, 2022
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef vector<int> vi;
  5.  
  6. vector<vi> AL;                                   // undirected tree
  7. vi par, heavy;
  8.  
  9. int heavy_light(int x) {                         // DFS traversal on tree
  10.   int size = 1;
  11.   int max_child_size = 0;
  12.   for (auto &y : AL[x]) {                        // edge x->y
  13.     if (y == par[x]) continue;                   // avoid cycle in a tree
  14.     par[y] = x;
  15.     int child_size = heavy_light(y);             // recurse
  16.     if (child_size > max_child_size) {
  17.       max_child_size = child_size;
  18.       heavy[x] = y;                              // y is x's heaviest child
  19.     }
  20.     size += child_size;
  21.   }
  22.   return size;
  23. }
  24.  
  25. vi group;
  26.  
  27. void decompose(int x, int p) {
  28.   group[x] = p;                                  // x is in group p
  29.   for (auto &y : AL[x]) {                        // edge x->y
  30.     if (y == par[x]) continue;                   // avoid cycle in a tree
  31.     if (y == heavy[x])
  32.       decompose(y, p);                           // y is in group p
  33.     else
  34.       decompose(y, y);                           // y is in a new group y
  35.   }
  36. }
  37.  
  38. int main() {
  39.   // as in Figure in HLD section, not yet rooted
  40.   int N = 19;
  41.   AL.assign(N,  {});
  42.   AL[0] = {1, 2, 3};
  43.   AL[1] = {0, 4};
  44.   AL[2] = {0, 5, 6, 7};
  45.   AL[3] = {0, 8};
  46.   AL[4] = {1, 9, 10};
  47.   AL[5] = {2};
  48.   AL[6] = {2};
  49.   AL[7] = {2, 11, 12};
  50.   AL[8] = {3};
  51.   AL[9] = {4};
  52.   AL[10] = {4, 13};
  53.   AL[11] = {7, 14};
  54.   AL[12] = {7, 15};
  55.   AL[13] = {10};
  56.   AL[14] = {11, 16};
  57.   AL[15] = {12, 17, 18};
  58.   AL[16] = {14};
  59.   AL[17] = {15};
  60.   AL[18] = {15};
  61.  
  62.   par.assign(N, -1);
  63.   heavy.assign(N, -1);
  64.   heavy_light(0); // start modified DFS from root 0
  65.   group.assign(N, -1);
  66.   decompose(0, 0); // start labeling paths
  67.   for (int i = 0; i < N; ++i)
  68.     cout << setw(2) << i << ", parent = " << setw(2) << par[i] << ", heaviest child = " << setw(2) << heavy[i] << ", belong to heavy-paths group = " << group[i] << "\n";
  69.  
  70.   return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment