spider68

Kruskal’s Algorithm

Jul 29th, 2021
715
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7. const int MAX = 1e5 + 5;
  8. int id[MAX], nodes, edges;
  9. pair <long long, pair<int, int> > p[MAX];
  10.  
  11. void initialize()
  12. {
  13.     for(int i = 0;i < MAX;++i)
  14.         id[i] = i;
  15. }
  16.  
  17. int root(int x)
  18. {
  19.     while(id[x] != x)
  20.     {
  21.         x = id[x];
  22.         // id[x] = id[id[x]];
  23.        
  24.     }
  25.     return x;
  26. }
  27.  
  28. void union1(int x, int y)
  29. {
  30.     int p = root(x);
  31.     int q = root(y);
  32.     id[p] = id[q];
  33. }
  34.  
  35. long long kruskal(pair<long long, pair<int, int> > p[])
  36. {
  37.     int x, y;
  38.     long long cost, minimumCost = 0;
  39.     for(int i = 0;i < edges;++i)
  40.     {
  41.         // Selecting edges one by one in increasing order from the beginning
  42.         x = p[i].second.first;
  43.         y = p[i].second.second;
  44.         cost = p[i].first;
  45.         // Check if the selected edge is creating a cycle or not
  46.         if(root(x) != root(y))
  47.         {
  48.             minimumCost += cost;
  49.             union1(x, y);
  50.         }    
  51.     }
  52.     return minimumCost;
  53. }
  54.  
  55. int main()
  56. {
  57.     int x, y;
  58.     long long weight, cost, minimumCost;
  59.     initialize();
  60.     cin >> nodes >> edges;
  61.     for(int i = 0;i < edges;++i)
  62.     {
  63.         cin >> x >> y >> weight;
  64.         p[i] = make_pair(weight, make_pair(x, y));
  65.     }
  66.     // Sort the edges in the ascending order
  67.     sort(p, p + edges);
  68.     minimumCost = kruskal(p);
  69.     cout << minimumCost << endl;
  70.     return 0;
  71. }
RAW Paste Data