kruskal 27s algorithm c 2b 2b hackerearth

Solutions on MaxInterview for kruskal 27s algorithm c 2b 2b hackerearth by the best coders in the world

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