Minimum Spanning Tree

Prim’s Algorithm:

1. Start with a node and mark it visited
2. Add all of it’s neighboring edges
3. Greedily choose the next smallest edge’s node and add it to the queue
   continue until there are no more nodes
   Verified here: https://www.geeksforgeeks.org/problems/minimum-spanning-tree/1

	int spanningTree(int n, vector<vector<int>>& edges) {
        // code here
        vector<vector<pair<int,int>>> adj(n);
        vector<int> minEdge = {0,0,INT_MAX};
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        for (auto edge: edges) {
            int from = edge[0];
            int to = edge[1];
            int cost = edge[2];
            adj[from].push_back({to, cost});
            adj[to].push_back({from, cost});
        }
 
        vector<bool> visited(n, false);
        pq.push({0,0});
        int totalSum = 0;
        while(!pq.empty()) {
            auto [curWeight, curNode] = pq.top();
            pq.pop();
            if (visited[curNode]) {
                continue;
            }
            visited[curNode] = true;
            totalSum += curWeight;
            for (auto [nextNode, weight]: adj[curNode]) {
                if (!visited[nextNode]) {
                    pq.push({weight, nextNode});
                }
            }
        }
        
        return totalSum;
    }

Kruskal’s Algorithm

Makes it so much simpler lol.
Just try joining all edges

// User function Template for C++
 
class DSU {
    private:
        vector<int> parent;
        vector<int> size;
    public:
        DSU(int n): parent(n, -1), size(n, 1) {
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        bool unite(int x, int y) {
            int par_x = find(x);
            int par_y = find(y);
            if (par_x == par_y) {
                // this means these both are already in the same component
                return false;
            }
            // small to large merging
            if (size[par_x] < size[par_y]) {
                swap(par_x, par_y);
            }
            parent[par_y] = par_x;
            size[par_x] += size[par_y];
            return true;
        }
};
 
class Solution {
  public:
    int kruskalsMST(int n, vector<vector<int>> &edges) {
        sort(edges.begin(), edges.end(), [&](vector<int>& a, vector<int>&b){
            return a[2] < b[2];
        });
        DSU dsu(n);
        int cost = 0;
        for (auto edge: edges) {
            if (dsu.unite(edge[0], edge[1])) {
                cost += edge[2];
            }
        }
        return cost;
    }
};