Optimize Water Distribution in a Village

There are N homes in a village, we have to facilitate water supply in each of them. We can either build a well in a home or connect it with pipe to some different home already having water supply. More formally, we can either build a new well in the home or connect it with a pipeline to some different home which either has it’s own well or further gets water supply from a different home and so on. There is some cost associated with both building a new well and laying down a new pipeline. We have to supply water in all homes and minimise the total cost.

Input- First line contains an integer N, the number of homes. The next line contains N integers, the ith integer denotes the cost of building a well in that home. Next line contains an integer K, then K lines follows. Each of which contains 3 integers i, j and p. Which denotes the cost ‘p’ of laying down pipeline between homes i and j.

Output- Output a single integer - the minimum cost to supply water to all the homes

class solution {
    public static int findParent(int[] parent, int n) {
        while (parent[n] != n)
            n = parent[n];
        return n;
    }

    public static int findMinCost(int n, int[][] edges, int[] wells) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        for (int[] edge : edges)
            pq.add(edge);
        // Dummy edges from wells
        for (int i = 0; i < n; i++)
            pq.add(new int[] { n, i, wells[i] });
        // Parent Array
        int[] parent = new int[n + 1];
        for (int i = 0; i <= n; i++)
            parent[i] = i;
        int minCost = 0;
        // This will make exactly n edges
        // Because we added 1 dummy node
        // therefore total nodes -> n+1
        // number of edges such that all receive water -> n
        while (pq.size() > 0) {
            int[] edge = pq.poll();
            int parentX = findParent(parent, edge[0]);
            parent[edge[0]] = parentX;
            int parentY = findParent(parent, edge[1]);
            parent[edge[1]] = parentY;
            if (parentX != parentY) {
                parent[parentX] = parentY;
                minCost += edge[2];
            }
        }
        return minCost;
    }
}