Untitled
unknown
plain_text
a year ago
1.7 kB
6
Indexable
class edge{ public: int u,v,c; edge(int u, int v, int c){ this->u=u; this->v=v; this->c=c; } }; bool cmp(edge a, edge b){ return a.c < b.c; } class Solution { public: int par[1001]; int groupsize[1001]; //Function to find sum of weights of edges of the Minimum Spanning Tree. int dsu_find(int node){ if(par[node] == -1) return node; int leader = dsu_find(par[node]); par[node] = leader; return leader; } void union_size(int node1, int node2){ int leaderA = dsu_find(node1); int leaderB = dsu_find(node2); if(groupsize[leaderA] > groupsize[leaderB]){ par[leaderB] = leaderA; groupsize[leaderA]+=groupsize[leaderB]; } else{ par[leaderA] = leaderB; groupsize[leaderB]+=groupsize[leaderA]; } } int spanningTree(int V, vector<vector<int>> adj[]) { // code here for(int i=0; i<V; i++) par[i] = -1; for(int i=0; i<V; i++) groupsize[i] = 1; vector<edge>edlist; for(int i=0; i<V; i++){ if(!adj[i].empty()){ for(auto child : adj[i]){ if(i<child[0]) edlist.push_back(edge(i,child[0],child[1])); } } } sort(edlist.begin(), edlist.end(), cmp); int cost = 0; for(auto ed : edlist){ int leaderA = dsu_find(ed.u); int leaderB = dsu_find(ed.v); if(leaderA == leaderB) continue; else{ union_size(ed.u,ed.v); cost+=ed.c; } } return cost; } };
Editor is loading...
Leave a Comment