Implement Water Supply System

Vaibhav Agarwal
Last Updated: May 13, 2022

Introduction

The problem states that we have N cities and N-1 roads connecting these N cities roads. The task is to set a water supply system, i.e we can set up a water pump in any city, let say i (1<=i<=N),  and then supply water to other cities using the road network. There is one limitation: some cities are blocked, i.e, if we come to any of the blocked cities, we cannot move to any other city from this blocked city.

Our task is to find the maximum number of cities to which water can be supplied by therefore using this water supply system

Input Format

  • The first line contains N, the total number of cities.
  • The next N-1 lines have x y denoting a road network between city x and y. 
  • The next line contains N spaced integers, either 0 or 1, indicating whether the city is blocked or not. 

 

Output Format

The only line contains a maximum number of cities to which water can be supplied. 

Sample Examples

Example 1:

Input:
4
3 4
2 3
1 2
0 1 1 0  

Output:
Maximum number of cities: 2
Explanation:
If we choose city 1, then we can supply the water to cities 1 and 2, and not go beyond that because city 2 is blocked.
If we choose city 2, then we can supply water to city 2, and not go beyond that because city 2 is blocked.
If we choose city 3, then we can supply water to city 3, and not go beyond that because city 2 is blocked.
If we choose city 4, then we can supply water to cities 4 and 3, and not go beyond that because city 3 is blocked.

 

Example 2:

Input:
7 
3 4 
1 2 
5 6 
2 3
4 5
6 7 
0 1 1 0 0 0 0 


Output:
Maximum number of cities: 5
Explanation:
If we choose city 1, then we can supply the water to cities 1 and 2, and not go beyond that because city 2 is blocked.
If we choose city 2, then we can supply water to city 2, and not go beyond that because city 2 is blocked.
If we choose city 3, then we can supply water to city 3, and not go beyond that because city 2 is blocked.
If we choose city 4, then we can supply water to cities 3,4,5,6, and 7. 
Similarly, for cities 5, 6, 7 we can supply water to 3,4,5,6, and 7 cities. 
Therefore the maximum number of cities to which water can be supplied using this water supply system is 5. 

Solution Approach(BFS)

The idea is to use the graph’s Breadth-First Search(BFS). 

Let’s recap what is BFS in brief -  This algorithm selects a single node (initial or source point) in a graph and then visits all the nodes adjacent to the selected node.

We run the BFS on each city and for the two conditions, i.e, the selected city should not be blocked and it is not already visited. If both the conditions hold true, then we run the breadth-first search from that city and count the maximum number of cities to which water can be supplied.

 

Algorithm

  1. Make a function BFSUtil() that will help to run the BFS over all the cities, and check for the condition whether the selected city is blocked or not and visited or not. 
  2. If both the conditions hold true, then we run the BFS on that city and find the maximum number of cities up to which water can be supplied through this city.
  3. We will keep one variable let say ‘result’ that always holds the maximum number of cities to which water can be supplied from any particular city. 
  4. At last, we will return this variable ‘result’. 

 

Implementation in C++

// C++ program to solve 
// water supply problem using BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to perform BFS on the selected city
int BFS(int blockedCity[], bool visited[], vector<int> adj[], int src)
{
    // Mark current source visited
    visited[src] = true;

    queue<int>q;
    q.push(src);

    int count = 0;
    while (!q.empty()) {

        int currCity = q.front();
        for(auto it : adj[currCity]){

            // When the adjacent city not visited and
            // not blocked, push city in the queue.
            if (!visited[it] && blockedCity[it] == 0) {
                count++;
                visited[it] = true;
                q.push(it);
            }
            // when the adjacent city is not visited
            // but blocked so the blocked city is
            // not pushed in queue
            else if (!visited[it] && blockedCity[it] == 1)
                count++;
        }
        q.pop();
    }
    return count + 1;
}


// Function that will run over all the cities to find maximum number cities.
int BFSUtil(int N, int blockedCity[], vector<int> adj[])
{
    // visited array to store whether the city is visited or not
    bool visited[N + 1];
    // variable to store final results as well as currValue
    int result = 1, currValue;

    // marking visited array false intially
    // as no city is visited for now.
    for (int i = 1; i <= N; i++)
        visited[i] = false;

    // running loop over every city
    for (int i = 1; i <= N; i++) {
        // checking the condition
        // city is not blocked and not visited
        if (blockedCity[i] == 0 && !visited[i]) {
            currValue = BFS(blockedCity, visited, adj, i);
            if (result < currValue) {
                result = currValue;
            }
        }
    }

    return result;
}

// Driver Code
int main()
{
    // N to store the number of cities
    int N = 4;
    // making the adjaceny list to hold the connection between the roads.
    vector<int> adj[N + 1];
    // vector to store which cities are blocked(1-base indexing)
    int blockedCity[N + 1];

    // Adjacency list denoting road
    // between city u and v
    adj[3].push_back(4);
    adj[4].push_back(3);
    adj[2].push_back(3);
    adj[3].push_back(2);
    adj[1].push_back(2);
    adj[2].push_back(1);

    // storing the conditions of the roads.
    blockedCity[1] = 0;
    blockedCity[2] = 1;
    blockedCity[3] = 1;
    blockedCity[4] = 0;

    // printing the maximum number of cities from water supply system
    cout<< "Maximum number of cities " << BFSUtil(N, blockedCity, adj) << endl;
    return 0;
}

 

Output:

Maximum number of cities 2.

 

Complexity Analysis

Time Complexity: O( |N| )

N is the number of cities. We will visit only the given number of cities only once, therefore the time complexity for the water supply system is O(|N|).

Space Complexity: O(| N |)

This space will be used by queue during the BFS; in a worst-case scenario, all the cities are connected with a single city. In. Therefore, the queue will store a maximum of N number of elements

Frequently asked questions

Q1. What is the difference between Breadth-first Search and Depth-first search? 

Ans. The BFS uses queue data structure while DFS uses the stack data structure. BFS is more suitable for searching vertices closer to the given source, while DFS is more suitable for solutions away from the source.

 

Q2. What is the maximum number of edges in the undirected graph of Nodes N? 

Ans. Each node can have an edge with every other n-1 node in an undirected graph. Therefore the total number of edges possible are n*(n-1)/2.

 

Q3. Which is the use of Djikstra’s Algorithm? 

Ans. It is used for finding the shortest path between nodes in a graph.

Key takeaways

In this article, we discussed the problem of implementing the water supply system. We hope you understand the problem and solution properly. Now you can do more similar questions. 

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think