Kruskal's Algorithm

kruskalsAlgo.cpp

class Solution
{
	public:
	//Function to find sum of weights of edges of the Minimum Spanning Tree.
	
	class Node {
	   public:
	   int wt, u, v;
	   Node() {}
	   Node(int wt, int u, int v) {
	       this->wt = wt;
	       this->u = u;
	       this->v = v;
	   }
	};
	int *parent;
	int *rank;
	
	void makeSet(int n) {
	    for(int i=0; i<n; i++) {
	        parent[i] = i;
	        rank[i] = 0;
	    }
	}
	
	int findParent(int node) {
	    if(parent[node] == node)
	        return node;
	        
	    return parent[node] = findParent(parent[node]);
	}
	
	void makeUnion(int u, int v) {
	    u = findParent(u);
	    v = findParent(v);
	    
	    if(rank[u] > rank[v]) {
	        parent[v] = u;
	    } else if(rank[u] < rank[v]) {
	        parent[u] = v;
	    } else {
	        parent[u] = v;
	        rank[v] += 1;
	    }
	}
	
    int spanningTree(int V, vector<vector<int>> adj[])
    {
        parent = new int[V+1];
        rank = new int[V+1];
        vector<Node> nodes;
        
        for(int i=0; i<V; i++) {
            for(auto it: adj[i]) {
                nodes.push_back(Node(it[1], i, it[0]));
            }
        }
        
        makeSet(V);
        
        sort(nodes.begin(), nodes.end(), [&](const Node &a, const Node &b) -> bool {
           return a.wt < b.wt; 
        });
        
        int mstW = 0;
        
        for(auto node: nodes) {
            if(findParent(node.u) != findParent(node.v)) {
                mstW += node.wt;
                makeUnion(node.u, node.v);
            }
        }
        
        return mstW;
    }
};