Advertisement
shawon_majid

DSU

Aug 14th, 2022
781
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.65 KB | None | 0 0
  1. const int mx = 2e5+10;
  2.  
  3. vector < int > parent(mx);
  4. vector < int > sz(mx);
  5.  
  6. int numberOfComponents;
  7.  
  8. void init(int n){
  9.     for(int i = 1; i <= n; i++){
  10.         parent[i] = i;
  11.         sz[i] = 1;
  12.     }
  13. }
  14.  
  15.  
  16. int findSet(int a){
  17.     if(parent[a] == a){
  18.         return a;
  19.     }
  20.     parent[a] = findSet(parent[a]);
  21.     return parent[a];
  22. }
  23.  
  24. void unionSet(int a, int b){
  25.     a = findSet(a);
  26.     b = findSet(b);
  27.  
  28.     if(a != b){
  29.         if(sz[a] >= sz[b]){
  30.             parent[b] = a;
  31.             sz[a] += sz[b];
  32.         }
  33.         else{
  34.             parent[a] = b;
  35.             sz[b] += sz[a];
  36.         }
  37.         numberOfComponents--;
  38.     }
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement