SHARE
TWEET

Disjoint set

keverman Feb 11th, 2019 (edited) 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct ds_node
  2. {
  3.     int par, size;
  4.    
  5.     ds_node()
  6.     {
  7.         size = 1;
  8.     }
  9. };
  10.  
  11. std::vector<ds_node> ds;
  12.  
  13. void build(int size)
  14. {
  15.     ds.resize(size);
  16.    
  17.     for(int i = 0; i < size; i++)
  18.         ds[i].par = i;
  19. }
  20.  
  21. int find(int u)
  22. {
  23.     if(u != ds[u].par) ds[u].par = find(ds[u].par);
  24.     return ds[u].par;
  25. }
  26.  
  27. void merge(int u, int v)
  28. {
  29.     if((u = find(u)) != (v = find(v)))
  30.     {
  31.         if(ds[u].size < ds[v].size) std::swap(u, v);
  32.         ds[v].par = ds[u].par;
  33.         ds[u].size += ds[v].size;
  34.     }
  35. }
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