Problem 45509. List the households affected by leaks in water distribution

Karl Ezra Pilario

23 solvers

4 likes

Solve

Solve Later

Consider the following water distribution network, where water is pumped uni-directionally from left to right:
             8
            /
           2 ---- 9     13      24 ---- 25
          / \          /       /      
         /   7        12 ---- 23
        /     6      / \           22
0 ---- 1     /      /   14        /
        \   4 ---- 11            /
         \ / \          17 ---- 19 ---- 21
          3   \        /  \      \
           \  10 ---- 15   18     \
            5          \           20
                        16
The network consists of: (1) a single source station; (2) pumping stations; and, (3) households / end-users. The source station is Node 0. Pumping stations are nodes that lead water to more nodes downstream. In the example, the pumping stations are Nodes 1, 2, 3, 4, 10, 11, 12, 15, 17, 19, 23, 24. Meanwhile, households are nodes that do not lead to any more nodes downstream. In the example, the households are Nodes 5, 6, 7, 8, 9, 13, 14, 16, 18, 20, 21, 22, 25.
If there is a leak at any node, then all the nodes downstream from that node will be affected, including itself. For instance, if Node 17 has leaked, then Nodes 17-22 are all affected. Among these, Nodes 18, 20-22 are households. Given P, can you list all the households that are affected by a leak in Node P?
Write a function that accepts a vector X, which is a row vector of length N, and a scalar P. The X represents the water distribution network, read as follows: Node X( i ) is a direct downstream water distributor to Node i, for 1 <= i <= N. Given X and P, output a row vector listing all affected households, sorted in increasing order.
For instance, the above example will be represented as:
i =  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
X = [0 1 1 3 3 4 2 2 2  4  4 11 12 12 10 15 15 17 17 19 19 19 12 23 24]
Please take the time to verify the elements of X. Using this X, sample test cases are given below:
>> water_loss(X,2)
ans =  
   7 8 9
>> water_loss(X,10)
ans =
   16 18 20 21 22
>> water_loss(X,23)
ans =
   25
>> water_loss(X,13)
ans =
   13
You are ensured that:
2 <= N <= 400 and 1 <= P <= N
X( i ) < i, for i = [1, N]
X( i ) > 0, for i = [2, N]