Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <algorithm>
- using namespace std;
- const int MAX = 1e5 + 5;
- int id[MAX], nodes, edges;
- pair <long long, pair<int, int> > p[MAX];
- void initialize()
- {
- for(int i = 0;i < MAX;++i)
- id[i] = i;
- }
- int root(int x)
- {
- while(id[x] != x)
- {
- x = id[x];
- // id[x] = id[id[x]];
- }
- return x;
- }
- void union1(int x, int y)
- {
- int p = root(x);
- int q = root(y);
- id[p] = id[q];
- }
- long long kruskal(pair<long long, pair<int, int> > p[])
- {
- int x, y;
- long long cost, minimumCost = 0;
- for(int i = 0;i < edges;++i)
- {
- // Selecting edges one by one in increasing order from the beginning
- x = p[i].second.first;
- y = p[i].second.second;
- cost = p[i].first;
- // Check if the selected edge is creating a cycle or not
- if(root(x) != root(y))
- {
- minimumCost += cost;
- union1(x, y);
- }
- }
- return minimumCost;
- }
- int main()
- {
- int x, y;
- long long weight, cost, minimumCost;
- initialize();
- cin >> nodes >> edges;
- for(int i = 0;i < edges;++i)
- {
- cin >> x >> y >> weight;
- p[i] = make_pair(weight, make_pair(x, y));
- }
- // Sort the edges in the ascending order
- sort(p, p + edges);
- minimumCost = kruskal(p);
- cout << minimumCost << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement