The Question
Coding

Optimize Water Distribution in a Village

There are $n$ houses in a village. You want to supply water to all the houses by building wells and laying pipes. For each house $i$, you can either build a well inside it directly with cost wells[i-1], or pipe water from another house to it. The cost to lay a pipe between house $u$ and house $v$ is given by the array pipes where each pipes[j] = [house1, house2, cost] represents a bidirectional connection. Return the minimum total cost to supply water to all houses. Constraints: - $1 \le n \le 10^4$ - wells.length == n - $0 \le wells[i] \le 10^5$ - $1 \le pipes.length \le 10^4$ - $1 \le house1, house2 \le n$ - $0 \le cost \le 10^5$ - $house1 \neq house2$
C++
Kruskal's Algorithm
MST
DSU
Questions & Insights

Clarifying Questions

What are the constraints on the number of houses ($n$) and the number of pipes?
Assumption: n and the number of pipes are up to 10^4. This implies an O(E \log E) or O(E \log V) approach is required.
Can there be multiple pipes between the same two houses or a pipe connecting a house to itself?
Assumption: Yes, multiple pipes may exist. Kruskal's algorithm naturally handles these by picking the one with the minimum weight. Self-loops are ignored by the Union-Find structure.
Are all costs (wells and pipes) non-negative?
Assumption: Costs are non-negative. If negative costs existed, the Minimum Spanning Tree (MST) approach would still find the minimum cost to connect all nodes, but we might want to include all negative edges even if they create cycles (though not relevant for a standard water distribution problem).
Is the graph guaranteed to be connected?
Assumption: Not necessarily through pipes alone, but every house has a well cost, ensuring a solution always exists (at worst, we build a well in every house).

Thinking Process

Model the "Well" as a Graph Edge: The core challenge is that a house gets water either from a pipe or a self-contained well. We can transform the "well" option into a standard edge by introducing a Virtual Node (Node 0). Building a well at house i with cost c_i is equivalent to adding an edge between Node 0 and Node i with weight c_i.
Formulate as an MST Problem: Once the virtual node is added, every house must be connected to either another house that has water or directly to the virtual node. This is exactly the definition of a Minimum Spanning Tree (MST) that spans all houses 1 \dots n and the virtual node 0.
Select the Algorithm: Since we are dealing with an edge-list representation and the graph is likely sparse or medium-density, Kruskal’s Algorithm using a Disjoint Set Union (DSU) with path compression and union by rank is highly efficient.
Edge Collection: Consolidate all pipe costs and the virtual "well" edges into a single list, sort them by weight, and greedily add edges that connect previously unconnected components until all n+1 nodes are in one component.
Implementation Breakdown

Problem Set

Functional Requirements:
Input: number of houses), wells (array of costs), pipes (array of triplets [h1, h2, cost]).
Output: Minimum total cost to supply water to all houses.
Constraints:
1 \le n \le 10,000
1 \le wells[i], pipes[j][2] \le 100,000
1 \le pipes.length \le 10,000

Approach

Algorithm: Kruskal's Algorithm
Data Structure: Disjoint Set Union (DSU) / Union-Find
Complexity:
Time: O(E \log E), where E = n + \text{pipes.length}. This is dominated by the sorting of edges.
Space: O(V + E) to store the edges and the DSU parent/rank arrays.

Implementation

Wrap Up

Advanced Topics

Prim's Algorithm: For very dense graphs (where pipes approach n^2), Prim's algorithm using a priority queue or a simple array (for O(V^2)) might be more efficient. However, in most distribution problems, the graph is sparse, favoring Kruskal's.
Hierarchical Clustering: This problem is essentially a variation of single-linkage clustering where we stop when all points are connected to a "centroid" (the virtual water source).
Distributed Computing: If n was massive (e.g., a country-wide grid), we could use Boruvka's algorithm, which is easier to parallelize as it grows components simultaneously in "rounds" rather than one edge at a time.
Robustness: In a real-world scenario, we might consider "K-extra edges" for redundancy (to ensure connectivity even if a pipe breaks). This moves the problem from MST toward finding a Minimum Cost k-Connected Subgraph, which is significantly harder (NP-hard for general k).