Minimum Spanning Trees (MST)

1584. Min Cost to Connect All Points

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

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

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;
}