Programming Problems #2 : Water Connection Problem
Solving a connected component problem using a graph algorithm
Today we will discuss the “Water Connection Problem”. This is an interesting problem and has been rated as “hard” across quite a few coding contest platforms. We will use a graph search algorithm to find the number of tanks and pipes to connect a set of buildings. We will go over the problem and implement the solution using Python.
Problem Statement
“Each building in our university has at most one pipe going into it and at most one pipe going out of it. Tanks and taps are to be installed in a manner such that every building with one outgoing pipe, but no incoming pipe gets a tank installed on its roof and each building with only an incoming pipe and no outgoing pipe gets a tap. Given 2 integers p and q denoting the number of buildings and the number of pipes. The connections of pipe among the houses contain three input values: a, b, d denoting the pipe of diameter d from building a to building b, develop an efficient solution for the network. The output will contain the number of pairs of tanks and taps t installed in first line and the next t lines contain three integers: building number of tanks, building number of tap and the minimum diameter of pipe between them.”
Example :
n=9
p=4Input
7, 4, 98
5, 9, 72
4, 6, 10
2, 8, 22Output
3
2 8 22
5 9 72
7 6 10
Solution
From the problem statement, we can make the following observations :
- A building with an outgoing pipe but no incoming pipe gets a tank installed.
- A building with an incoming pipe but no outgoing pipe gets a tap.
From the sample input, we can draw a directed graph of the connections of the different components/building to determine the number of tanks and taps to be fitted.
The above figure represents the connected buildings provided in the input as a graph. Let’s find out where to place tanks and taps in this configuration.
- In 5->9, 5 only has an outgoing pipe, hence it will have a tank installed. 9 only has an incoming pipe so it will have a tap installed. Since there are no other buildings connected, the minimum diameter will be 72.
- Similarly in 2->8, 2 has an outgoing pipe hence a tank and 8 has an incoming pipe, hence a tap. Here the minimum diameter is 22.
- In the connected components 7->4->6, 7 has an outgoing pipe hence it will have a tank installed. 4 has an incoming pipe and an outgoing pipe, so does not match any of the conditions given to us in the problem, so we neither place a tank nor tap in building 4. 6 has an incoming pipe only, so it has a tap. The minimum diameter of this configuration is 10<98, 10.
From 1,2&3 we can infer that the first and last buildings are the tank-tap pairs. Hence, when we have multiple connected components, we have to traverse the nodes in order of depth, using depth first search (DFS) to find the very last node. The code for this solution is provided below. In case you are new to depth first search you can read about here.
References
