SHARE
TWEET

MST_Kruskal

adnan_dipta89 Oct 21st, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. vector<vector<ll>> MSTedges;
  5. vector<vector<ll>> edges;
  6. ll N,M;
  7. class disjointSet
  8. {
  9.     public:
  10.     ll *_rank, *parent,n;
  11.     disjointSet(ll n)
  12.     {
  13.         _rank = new ll[n+1];
  14.         parent =  new ll[n+1];
  15.         this->n = n;
  16.         MakeSet();
  17.     }
  18.     void MakeSet()
  19.     {
  20.         for(ll i = 1; i <= n; i++)
  21.         {
  22.             parent[i] = i;
  23.             _rank[i] = 0;
  24.         }
  25.     }
  26.  
  27.     void Union(ll x, ll y)
  28.     {
  29.         ll xroot = Find(x);
  30.         ll yroot = Find(y);
  31.  
  32.         if(_rank[xroot] > _rank[yroot])
  33.         {
  34.             parent[yroot] = xroot;
  35.         }
  36.         else
  37.         {
  38.             parent[xroot] = yroot;
  39.             if(_rank[x] == _rank[y])
  40.                 _rank[x] = _rank[x]+1;
  41.         }
  42.     }
  43.  
  44.     ll Find(ll x)
  45.     {
  46.         if(x != parent[x])
  47.         {
  48.             parent[x] = Find(parent[x]);
  49.         }
  50.         return parent[x];
  51.     }
  52. };
  53.  
  54. bool compare(vector<ll> a, vector<ll> b)
  55. {
  56.    if(a[2] == b[2])
  57.    {
  58.        return a[0]+a[1]+a[2] < b[0]+b[1]+b[2];
  59.    }
  60.    return a[2] < b[2];
  61. }
  62.  
  63. void MST_Kruskal(ll N)
  64. {
  65.     disjointSet obj(N);
  66.     sort(edges.begin(),edges.end(),compare);
  67.     for(ll i = 0; i < edges.size(); i++)
  68.     {
  69.         ll u = edges[i][0];
  70.         ll v = edges[i][1];
  71.         if(obj.Find(u) != obj.Find(v))
  72.         {
  73.             MSTedges.push_back(edges[i]);
  74.             obj.Union(u,v);
  75.         }
  76.     }
  77. }
  78. int main()
  79. {
  80.     ll total_w = 0;
  81.     cin >> N >> M;
  82.     for(ll i = 0; i < M; i++)
  83.     {
  84.         ll u, v, w;
  85.         vector<ll> a;
  86.         cin >> u >> v >> w;
  87.         a.push_back(u);
  88.         a.push_back(v);
  89.         a.push_back(w);
  90.         edges.push_back(a);
  91.     }
  92.     MST_Kruskal(N);
  93.     for(ll i = 0; i < MSTedges.size(); i++)
  94.     {
  95.         total_w += MSTedges[i][2];
  96.     }
  97.     cout << total_w << endl;
  98.     return 0;
  99. }
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