# 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