Advertisement
bero_0401

dsu

Jul 18th, 2024
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.62 KB | Source Code | 0 0
  1. vector <int> parent(N);
  2. vector <int> link(N);
  3.  
  4. int find(int u )
  5. {
  6.     while(u!= parent[u])
  7.     {
  8.         u = parent[u];
  9.     }
  10.     return u;
  11. }
  12.  
  13.  
  14. bool same(int u , int v)
  15. {
  16.     return (find(u) == find(v));
  17. }
  18.  
  19. void Union(int u , int v)
  20. {
  21.     if(same(u , v))
  22.         return;
  23.     int p1 = find(u);
  24.     int p2 = find(v);
  25.     if(link[p1] < link[p2])
  26.     {
  27.         swap(p1 , p2);
  28.     }
  29.     link[p1] += link[p2];
  30.     parent[p2] = p1;
  31.  
  32.  
  33.  
  34. }
  35. void remove(int u , int v)
  36. {
  37.     int p = find(u);
  38.     if(link[p] < 2*link[u])
  39.     {
  40.         swap(p , u);
  41.     }
  42.     link[p] -= link[u];
  43.     parent[u] = u;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement