使用廣度優先搜尋實現供水問題

---

在這個問題中，我們將找到可以供水的最大城市數量。

我們可以將此問題視為遍歷阻塞節點的圖。因此，我們可以使用廣度優先搜尋演算法來查詢最大數量的連線城市。

問題陳述

我們給定總共 N 個城市。此外，我們還給定了兩個城市之間的邊；所有城市都與任何其他單個或多個城市連線。我們需要在每個城市建立供水連線。我們還給定了包含 0 和 1 值的 blocked[] 陣列。值 1 表示城市被阻塞。因此，我們不能透過該特定城市輸水。值 0 表示我們可以透過該城市輸水。我們需要找到可以供水的最大城市數量。

示例

輸入

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

輸出

4

解釋

如果我們從第 3 個或第 4 個城市開始供水，我們可以向第 2、3、4 和 5 個城市供水。

輸入

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

解釋

我們可以將水連線到第 2 個城市，以便向第 1、2、3 和 4 個城市供水。

方法

在這種方法中，我們將使用廣度優先搜尋演算法找到所有連線城市的集合。之後，我們可以將最大連線最大城市的集合的大小作為答案。

演算法

• 步驟 1 - 使用 false 布林值初始化 visited[] 陣列，以跟蹤在 BFS 遍歷期間是否訪問了該城市。

• 步驟 2 - 使用 1 初始化 maxi 以跟蹤最大連線城市。

• 步驟 3 - 使用迴圈遍歷每個城市。如果城市未被阻塞且之前未被訪問過，則呼叫 findConnectedCities() 函式以查詢當前城市的所有連線城市。

• 步驟 3.1 - 在 findConnectedCities() 函式中，將當前城市標記為已訪問。

• 步驟 3.2 - 定義佇列並將源城市插入佇列。此外，使用 0 初始化 'cnt' 以儲存連線城市的數目。

• 步驟 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 遍歷並查詢連線的節點。