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
- 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.
- 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.
- 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.
- 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
40+ registered 
