peltorator

Центроидная Декомпозиция

Feb 22nd, 2017
287
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int MAXN = 200007;
  2.  
  3. vector<int> g[MAXN], used, p, d;
  4.  
  5. int cnt;
  6.  
  7. int dfs(int v, int pr)
  8. {
  9.     cnt++;
  10.     d[v] = 1;
  11.     for (int u : g[v])
  12.         if (!used[u] && u != pr)
  13.             d[v] += dfs(u, v);
  14.     return d[v];
  15. }
  16.  
  17. int centroid(int v)
  18. {
  19.     cnt = 0;
  20.     dfs(v, -1);
  21.     int pr = -1;
  22.     while (true)
  23.     {
  24.         int z = -1;
  25.         for (int u : g[v])
  26.             if (!used[u] && u != pr && d[u] * 2 >= cnt)
  27.                 z = u;
  28.         if (z == -1)
  29.             break;
  30.         pr = v;
  31.         v = z;
  32.     }
  33.     return v;
  34. }
  35.  
  36. void go(int v, int pr)
  37. {
  38.     v = centroid(v);
  39.     p[v] = pr;
  40.     used[v] = 1;
  41.  
  42.  
  43.     for (int u : g[v])
  44.         if (!used[u])
  45.             go(u, v);
  46. }
RAW Paste Data