Untitled

 avatar
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