Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int g_nodes, g_edges, f, t, w;
- vector<int> parent(3001, -1);
- int root(int x){
- if(x == parent[x])
- return x;
- return root(parent[x]);
- }
- void unio(int x, int y){
- int p = root(x);
- int q = root(y);
- parent[p] = parent[q];
- }
- void kruskals(pair<int, pair<int, int> > g[]) {
- int cost = 0;
- sort(g, g+g_edges);
- for(int i=1; i<=g_nodes; ++i)
- parent[i] = i;
- for(int i=0; i<g_edges; ++i){
- int x = g[i].second.first;
- int y = g[i].second.second;
- if(root(x) != root(y)){
- unio(x, y);
- cost += g[i].first;
- }
- }
- cout<<cost<<endl;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin>>g_nodes>>g_edges;
- pair<int, pair<int, int> > g[g_edges];
- for (int i = 0; i < g_edges; i++) {
- cin>>f>>t>>w;
- g[i] = make_pair(w, make_pair(f, t));
- }
- kruskals(g);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement