C++ 使用广度优先搜索实现供水问题

在这个问题中，我们将找到我们可以供水的城市的最大数量。

我们可以将这个问题看作是一个遍历被阻塞节点的图。因此，我们可以使用广度优先搜索算法来找到最大数量的连通城市。

问题陈述

我们已经给出了总共N个城市。同时，我们给出了两个城市之间的边；所有城市都与另一个或多个城市相连。我们需要在每个城市建立供水连接。我们还给出了包含0和1值的blocked[]数组。值1表示该城市被阻塞，所以我们不能通过该特定城市输送水。值0表示我们可以通过该城市输送水。我们需要找出我们可以供水的最大数量的城市。

示例示例

输入

cities = 5; roads = 1-> 2, 2 -> 3, 3-> 4, 4-> 5; blocked[] = {0, 1, 0, 0, 1};

输出

4

解释

如果我们从第三或第四个城市开始供水，我们可以为第二、三、四和五个城市供水。

输入

cities = 5; roads = 1-> 2, 2 -> 3, 3-> 4, 4-> 5; blocked[] = {1, 1, 1, 1, 1};

输出

1

说明

当所有城市都被封锁时，我们可以为任何与供水连接的单个城市提供水源。

输入

cities = 6; roads = 1-> 2, 2 -> 3, 2 -> 6, 3-> 4, 4-> 5; blocked[] = {1, 0, 0, 1, 0, 1};

输出

4

解释

我们可以连接水管到第二个城市，向第一、二、三和四个城市供水。

方法

在这个方法中，我们将使用广度优先搜索算法找到所有连接的城市集合。然后，我们可以将连接的最大城市数量作为答案。

算法

• 第1步 - 初始化visited[]数组为false布尔值，用于追踪城市在BFS遍历中是否被访问过。

• 第2步 - 初始化maxi为1，用于追踪连接的最大城市数量。

• 第3步 - 使用循环遍历每个城市。如果城市未被封锁并且之前未被访问过，调用findConnectedCities()函数来找到所有与当前城市连接的城市。

• 第3.1步 - 在findConnectedCities()函数中，将当前城市标记为已访问。

• 第3.2步 - 定义队列并将源城市插入队列中。同时，初始化’cnt’为0，用于存储连接的城市数量。

• 第3.3步 - 在队列非空的情况下遍历队列。

• 第3.3.1步 - 弹出队列的第一个元素。

• 第3.3.2步 - 遍历当前城市的所有相邻城市。

• 第3.3.3步 - 如果城市未被访问过或未被封锁，将’cnt’增加1并将其标记为已访问，插入队列中。

• 第3.3.4步 - 如果城市未被访问过并且城市被封锁，将’cnt’增加1。

• 第3.3.5步 - 从队列中弹出城市。

• 第3.4步 - 返回cnt + 1。这里，我们加1是为了计算源城市本身。

• 第4步 - 如果从函数返回的值大于maxi，则将maxi更新为新值。

• 第5步 - 返回maxi。

例子

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int findConnectedCities(int blocked[], bool visited[], vector<int> roads[], int source) {
   visited[source] = true;
   queue<int> que;
   que.push(source);
   int cnt = 0;
   while (!que.empty()) {
      int temp = que.front();
      for (int p = 0; p < roads[temp].size(); p++) {
         // When the neighboring city is not blocked and visited
         if (!visited[roads[temp][p]] && blocked[roads[temp][p]] == 0) {
            cnt++;
            visited[roads[temp][p]] = true;
            que.push(roads[temp][p]);
         }
         // We can supply water to the blocked city, but the block city can't supply water to other cities
         else if (!visited[roads[temp][p]] && blocked[roads[temp][p]] == 1) {
            cnt++;
         }
      }
      que.pop();
   }
   return cnt + 1;
}
int maxNumberCities(int cities, int blocked[], vector<int> roads[]) {
   bool visited[cities + 1];
   int maxi = 1;
   for (int p = 1; p <= cities; p++)
      visited[p] = false;
   // Start BFS for each city
   for (int p = 1; p <= cities; p++) {
      // When the city is not blocked and not visited
      if (blocked[p] == 0 && !visited[p]) {
         int temp = findConnectedCities(blocked, visited, roads, p);
         if (temp > maxi) {
            maxi = temp;
         }
      }
   }
   return maxi;
}
int main() {
   int cities = 5;
   vector<int> roads[cities + 1];
   // To store road connection
   roads[1].push_back(2);
   roads[2].push_back(1);
   roads[2].push_back(3);
   roads[3].push_back(2);
   roads[3].push_back(4);
   roads[4].push_back(3);
   roads[3].push_back(5);
   roads[5].push_back(3);
   // To store whether the city is blocked or not
   int blocked[] = {0, 1, 0, 0, 1};
   cout << "The maximum number of cities to which we can supply water is " << maxNumberCities(cities, blocked, roads);
   return 0;
}

输出结果

The maximum number of cities to which we can supply water is 4

• 时间复杂度 - O(N) 用于遍历所有的城市。

• 空间复杂度 - O(N) 用于存储队列中的城市。

结论

给定的问题与寻找最大岛屿的大小非常相似。在岛屿问题中，我们也是从未访问的节点开始BFS遍历并找出相连的节点。