Fshl0

Kruskal

Jul 11th, 2020
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll root (ll x) {
  2.     while (id[x] != x)
  3.         x = id[x];
  4.     return x;
  5. }
  6.  
  7. ll Union (ll x, ll y) {
  8.     ll p = root(x), q = root(y);
  9.     if (p != q) {
  10.         if (sz[p] < sz[q])
  11.             swap(p, q);
  12.         id[q] = p;
  13.         sz[p] += sz[q];
  14.     }
  15. }
  16.  
  17. ll Kruskal () {
  18.     ll shit = 0;
  19.     for (ll i = 0; i < edges.size(); i++) {
  20.         ll cost = edges[i].F;
  21.         ll u = edges[i].S.F;
  22.         ll v = edges[i].S.S;
  23.         if (root(u) != root(v)) {
  24.             Union(u, v);
  25.             shit += cost;
  26.         }
  27.     }
  28.     return shit;
  29. }
RAW Paste Data