# 1168.Optimize-Water-Distribution-in-a-Village

There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.

For each house i, we can either build a well inside it directly with cost wells[i], or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes, where each pipes[i] = [house1, house2, cost] represents the cost to connect house1 and house2 together using a pipe. Connections are bidirectional.

Find the minimum total cost to supply water to all houses.

Example 1:

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]

Output: 3

Explanation:

The image shows the costs of connecting houses using pipes.

The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

Constraints:

1 <= n <= 10000

wells.length == n

0 <= wells[i] <= 10^5

1 <= pipes.length <= 10000

1 <= pipes[i][0], pipes[i][1] <= n

0 <= pipes[i][2] <= 10^5

pipes[i][0] != pipes[i][1]

Time: O(1) && Space: O(1)

class Solution {

class UnionFind {

int[] parent;

public UnionFind(int n) {

parent = new int[n];

for (int i = 0; i < n; i++) {

parent[i] = i;

}

}

public int find(int x) {

if (x != parent[x]) {

parent[x] = find(parent[x]);

}

return parent[x];

}

public void union(int x, int y) {

int px = find(x);

int py = find(y);

if (px == py) return;

parent[px] = py;

}

}

public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {

UnionFind uf = new UnionFind(n + 1);

List<int[]> edges = new ArrayList<>();

for (int i = 0; i < n; i++) {

edges.add(new int[]{0, i + 1, wells[i]});

}

for (int[] pipe: pipes) {

edges.add(pipe);

}

Collections.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

int res = 0;

for (int[] edge: edges) {

int x = edge[0];

int y = edge[1];

if (uf.find(x) == uf.find(y))

continue;

uf.union(x, y);

res += edge[2];

}

return res;

}

}

Last modified 3yr ago