daily pastebin goal
16%
SHARE
TWEET

Kruskal's algorithm

keverman Feb 13th, 2018 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct node
  2. {
  3.     int sz, parent;
  4. };
  5.  
  6. struct edge
  7. {
  8.     int from, to, weight;
  9.    
  10.     edge(int from, int to, int weight)
  11.     {
  12.         this -> from = from;
  13.         this -> to = to;
  14.         this -> weight = weight;
  15.     }
  16. };
  17.  
  18. bool edgeSorter(const edge &lhs, const edge &rhs)
  19. {
  20.     return lhs.weight > rhs.weight;
  21. }
  22.  
  23. int f(int x)
  24. {
  25.     while(DS[x].parent != x) return DS[x].parent = f(DS[x].parent);
  26.     return DS[x].parent;
  27. }
  28.  
  29. void unite(int x, int y)
  30. {
  31.     if(DS[x].parent != DS[y].parent)
  32.     {
  33.         if(DS[x].sz < DS[y].sz) std::swap(x, y);
  34.  
  35.         DS[y].parent = DS[x].parent;
  36.         DS[x].sz += DS[y].sz;
  37.         DS[y].sz = 0;
  38.     }
  39. }
  40.  
  41. std::vector<edge> MST()
  42. {
  43.     std::sort(edges.begin(), edges.end(), edgeSorter);
  44.     std::vector<edge> ret;
  45.    
  46.     for(unsigned int i = 0; i < edges.size(); i++)
  47.     {
  48.         int u = edges[i].from, v = edges[i].to;
  49.        
  50.         if(f(u) != f(v))
  51.         {
  52.             ret.push_back(edges[i]);
  53.             unite(u, v);
  54.         }
  55.     }
  56.    
  57.     return ret;
  58. }
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