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

public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] visited = new boolean[n];
    int[] minDist = new int[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    minDist[0] = 0;

    int result = 0;

    for (int i = 0; i < n; i++) {
        int curt = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (curt == -1 || minDist[j] < minDist[curt])) {
                curt = j;
            }
        }
        visited[curt] = true;
        result += minDist[curt];
        for (int j = 0; j < n; j++) {
            if (visited[j]) continue;
            int cost = Math.abs(points[curt][0] - points[j][0]) + Math.abs(points[curt][1] - points[j][1]);
            if (minDist[j] > cost) {
                minDist[j] = cost;
            }
        }
    }
    return result;
}

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

public int minimumCost(int n, int[][] connections) {
        // Build adjacency map: city -> list of (neighbor, cost)
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] conn : connections) {
            graph.get(conn[0]).add(new int[]{conn[1], conn[2]});
            graph.get(conn[1]).add(new int[]{conn[0], conn[2]});
        }

        boolean[] visited = new boolean[n + 1];
        int[] minCost = new int[n + 1];
        Arrays.fill(minCost, Integer.MAX_VALUE);
        minCost[1] = 0; // Start from city 1

        int result = 0, count = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{1, 0}); // [city, cost]

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int city = curr[0];
            int cost = curr[1];
            if (visited[city]) continue;

            visited[city] = true;
            result += cost;
            count++;

            for (int[] next : graph.get(city)) {
                int nextCity = next[0];
                int nextCost = next[1];
                if (!visited[nextCity] && nextCost < minCost[nextCity]) {
                    minCost[nextCity] = nextCost;
                    pq.offer(new int[]{nextCity, nextCost});
                }
            }
        }

        return (count == n) ? result : -1;
    }

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

public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
    // Build graph
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int i = 0; i <= n; i++) {
        graph.put(i, new ArrayList<>());
    }
    // Add edges from virtual node 0 to each house with well cost
    for (int i = 1; i <= n; i++) {
        graph.get(0).add(new int[]{i, wells[i-1]});
        graph.get(i).add(new int[]{0, wells[i-1]});   
    }
    for (int[] pipe : pipes) {
        int house1 = pipe[0];
        int house2 = pipe[1];
        int cost = pipe[2];
        graph.get(house1).add(new int[]{house2, cost});
        graph.get(house2).add(new int[]{house1, cost});
    }

    int[] minCost = new int[n + 1];
    Arrays.fill(minCost, Integer.MAX_VALUE);
    minCost[0] = 0;
    boolean[] visited = new boolean[n + 1];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);
    pq.offer(new int[]{0, 0});

    int result = 0;
    while (!pq.isEmpty()) {
        int[] curt = pq.poll();
        int house = curt[0], cost = curt[1];
        if (visited[house]) continue;

        visited[house] = true;
        result += cost;

        for (int[] next : graph.get(house)) {
            int nextHouse = next[0], nextCost = next[1];
            if (!visited[nextHouse] && nextCost < minCost[nextHouse]) {
                minCost[nextHouse] = nextCost;
                pq.offer(new int[]{nextHouse, nextCost});
            }
        }
    }
    return result;
}