1168. Optimize Water Distribution in a Village

[ErdemT09]

Resolves: #211

Before talking about this problem, it's best to review previous problems on Union-Find:

332, Union-Find Solution

329

200

These two problems also provide us great templates for efficient directed/undirected graph creation:

330

332, DFS Solution

Algorithm:

What does it mean to have a well here? A well from a house is just a weighted edge to some water-source vertex, a weighted edge like all pipes between the houses, which are also vertices. What we should do is then connect all these vertices, the water source and the houses, with minimum cost. This is nearly the exact same problem we had in #24. We have to find the minimum spanning tree (MST) for this graph of wells as edges from a water source and houses with pipes. There are two ways of doing this:

Approach 1-Union-Find/Kruskal

A visualization of this from Wikipedia This classical Union-Find approach begins by adding all edges of this graph to a priority queue (using sorting is also possible). We poll the shortest edge from it each time. If the root of two vertices of this edge are equal, they are already connected and we don't need to connect them again. Else, we connect them and assign parents using the rank system. We add the edge's cost to the total and decrement the number of unconnected components until we are left with 1, when we have "connected" all the vertices.

Approach 2-Prim's Algorithm

A visualization of this from Wikipedia Instead of picking the smallest edge from the entire graph, we can begin with some node (preferably the water source) and add nodes to this tree by selecting the shortest edge connected to this tree. If we add some node a to the tree, we also add all of its unvisited nodes to the priority queue to visit them. When the number of elements in the tree equal to n (we don't count the water source) that means that all houses are connected and we can return the costs.

[ErdemT09]

Union-Find is faster than the Prim's algorithm. Prim's algorithm might be slower because of the extensive graph creation and the number of edges being processed in the heap.

[altay9]

Thanks for drawing Erdem. It'll help a lot.