Minimum Spanning Trees (MST)

1584. Min Cost to Connect All Points

Kruskal

class UnionFind {
    vector<int> root;

public:
    UnionFind(int n) {
        root.resize(n);
        iota(root.begin(), root.end(), 0);
    }

    int find(int p) {
        while (p != root[p]) {
            root[p] = root[root[p]]; // Path compression
            p = root[p];
        }
        return p;
    }

    void connect(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA != rootB) {
            root[rootA] = rootB;
        }
    }
};

class Solution {
private:
    vector<array<int, 3>> edges;

    int getDist(int i, int j, const vector<vector<int>>& points) {
        return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
    }

public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n == 1) return 0;

        // Generate all unique edges (i, j, cost)
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                edges.push_back({i, j, getDist(i, j, points)});
            }
        }

        // Sort edges by cost
        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
            return a[2] < b[2];
        });

        UnionFind uf(n);
        int cost = 0, connected = 0;

        // Kruskal's algorithm
        for (const auto& e : edges) {
            int a = e[0], b = e[1], w = e[2];
            if (uf.find(a) != uf.find(b)) {
                uf.connect(a, b);
                cost += w;
                connected++;
                if (connected == n - 1) return cost;
            }
        }

        return -1; // Should not happen for valid input
    }
};

Prim

1135. Connecting Cities With Minimum Cost

Kruskal

class UnionFind {
    private:
        vector<int> root;
        vector<int> weights;

    public:
        UnionFind(int n) {
            root.resize(n);
            weights.resize(n, 1);
            iota(root.begin(), root.end(), 0);
        }

        int find(int p) {
            while (p != root[p]) {
                root[p] = root[root[p]];
                p = root[p];
            }
            return p;
        }

        void connect(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (weights[rootX] > weights[rootY]) {
                root[rootY] = rootX;
            } else {
                root[rootX] = rootY;
            }
        }
};


class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b){
            return a[2] < b[2];
        });
        UnionFind uf(n + 1);
        int cost = 0, edges = 0;
        for (const auto& conn: connections) {
            int a = conn[0], b = conn[1];
            int rootA = uf.find(a), rootB = uf.find(b);
            if (rootA != rootB) {
                uf.connect(a, b);
                cost += conn[2];
                edges += 1;
            }
        }
        return edges == n - 1 ? cost : -1;
    }
};

Prim

1168. Optimize Water Distribution in a Village

Kruskal

class UnionFind {
    vector<int> parent;

public:
    UnionFind(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);  
        }
        return parent[x];
    }

    bool connect(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA == rootB) return false;
        parent[rootA] = rootB;
        return true;
    }
};

class Solution {
private:
    vector<array<int, 3>> edges;

public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        for (int i = 0; i < wells.size(); ++i) {
            edges.push_back({i + 1, 0, wells[i]});   
        }
        for (vector<int> p : pipes) {
            edges.push_back({p[0], p[1], p[2]});
        }
        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b){
            return a[2] < b[2];
        });
        UnionFind uf(n + 1);
        int total_cost = 0, count = 0;
        for (const auto& [a, b, cost] : edges) {
            if (uf.connect(a, b)) {
                total_cost += cost;
            }
        }
        return total_cost;
    }
};

Prim