從樹中刪除一個頂點後，查詢連通分量的數量

以下查詢可用來決定刪除樹頂點後剩餘的連通分量：首先考慮樹結構。然後，透過使用廣度優先或深度優先搜尋演算法在樹中移動，檢查每個連接的組件。一旦所需的頂點被驅逐，就使用相同的遍歷方法來決定連接組件的數量。結果將根據開除前後計數的變化來決定。該方法有效地監視連接變化並幫助計算更新樹中的連接組件。

使用的方法

• 深度優先搜尋 (DFS) 方法

• 並查法

深度優先搜尋 (DFS) 方法

在 DFS 方法中，我們首先從原始樹中的任何選定節點執行 DFS 遍歷，以在從樹中刪除頂點後對連接的元件進行計數。在此遍歷過程中，我們遍歷每個連接的節點，將每個節點標記為已訪問，並追蹤使用 DFS 的次數。我們在刪除指定頂點後執行新的 DFS 遍歷，確保在探索階段跳過刪除的頂點。我們可以透過比較刪除前後呼叫 DFS 的次數來確定更新樹中連通分量的數量。這種方法可以有效地計算連接元素的數量，同時根據樹結構的變化進行調整。

演算法

• 選取原樹上的任一個頂點作為DFS遍歷的起點。

• 設定變數「count」以開始對連接的元件進行計數。首先，將其設為 0。

• 從選定的起始頂點，使用 DFS 遍歷樹。

• 標記 DFS 遍歷期間存取的每個頂點，並為每個新的 DFS 呼叫（即，對於找到的每個連接元件）將「計數」增加 1。

• DFS遍歷完成後，原樹中連通元素的數量將以「count」表示。

• 從樹中刪除指定的頂點。

• 從相同起始頂點重複 DFS 遍歷，確保避免探索已刪除的頂點。

• 在執行 DFS 時，與先前類似地更新「count」變數。

• 升級後的樹中關聯組件的數量將透過從開始的「計數」中減去疏散後的「計數」來確定。

範例

#include <iostream>
#include <vector>

void dfs(const std::vector<std::vector<int>>& tree, int v, 
std::vector<bool>& visited, int& count) {
   visited[v] = true;
   count++;
   for (int u : tree[v]) {
      if (!visited[u]) {
         dfs(tree, u, visited, count);
      }
   }
}

int countConnectedComponents(const std::vector<std::vector<int>>& tree, int startVertex) {
   int n = tree.size();
   std::vector<bool> visited(n, false);
   int count = 0;

   dfs(tree, startVertex, visited, count);
   return count;
}

int main() {
   std::vector<std::vector<int>> tree = {
      {1, 2},
      {0, 3},
      {0, 4},
      {1},
      {2}
   };

   int startVertex = 0;
   std::cout << countConnectedComponents(tree, startVertex) << std::endl;
   return 0;
}

輸出

5

並查法

我們首先在並尋找方法中將每個頂點初始化為單獨的元件，以便在從樹中刪除頂點後對連接的元件進行計數。為了追蹤原始樹中的部件和連接，我們採用並尋找資料結構。我們更新並檢查資料結構以反映刪除指定頂點後樹的連通性的變化。然後計算並檢查資料結構中不同集合的數量。得到的計數代表了樹的更新組件的連通性。刪除頂點後，並尋找方法可以有效計算連通分量並有效處理樹中的結構變化。

演算法

• 從頭開始建立一個陣列或資料結構，將每個頂點表示為樹的不同部分。最初，每個頂點都是自己的父頂點。

• 在預處理步驟中使用並尋找操作來確定原始樹的連接元件計數。

• 使用並查資料結構來組合樹中每條邊 (u, v) 包含頂點 u 和 v 的部分。樹的初始連通性在此步驟中建立。

• 從樹中刪除指定的頂點。

• 將預處理步驟的並尋找操作套用到修改後的樹。

• 刪除後，計算並檢視資料結構中不同父代代表的數量。

• 結果計數代表了樹更新元件的連通性。

範例

#include <iostream>
#include <vector>

class UnionFind {
public:
   UnionFind(int n) {
      parent.resize(n);
      for (int i = 0; i < n; ++i) {
         parent[i] = i;
      }
   }

   int find(int u) {
      if (parent[u] != u) {
         parent[u] = find(parent[u]);
      }
      return parent[u];
   }

   void unite(int u, int v) {
      int rootU = find(u);
      int rootV = find(v);
      if (rootU != rootV) {
         parent[rootU] = rootV;
      }
   }

   int countDistinctParentRepresentatives() {
      int n = parent.size();
      std::vector<bool> distinct(n, false);
      for (int i = 0; i < n; ++i) {
         distinct[find(i)] = true;
      }
      int count = 0;
      for (bool isDistinct : distinct) {
         if (isDistinct) {
            count++;
         }
      }
      return count;
   }

private:
   std::vector<int> parent;
};

int main() {
   int n = 5;
   UnionFind uf(n);

   uf.unite(0, 1);
   uf.unite(0, 2);
   uf.unite(2, 3);
   uf.unite(2, 4);

   std::cout << uf.countDistinctParentRepresentatives() << 
std::endl;
   return 0;
}

輸出

1

結論

總之，所提供的方法可以有效地計算刪除特定頂點後樹中連接部分的數量。使用深度優先搜尋 (DFS) 方法和並尋找方法可以有效地處理樹結構中的連結性變化。 DFS 方法從選取頂點開始遍歷，標記造訪過的每個節點，並統計連接的元件。更新後的計數是透過比較刪除頂點後的前後遍歷計數來獲得的，並且在不包括刪除的節點的情況下執行新的遍歷。

初始連接組件計數是透過 Union-Find 方法使用並集運算來確定的，該方法將每個頂點初始化為單獨的組件。刪除頂點後套用相同的並集操作，並對不同的父代表進行計數以獲得更新的計數。

刪除頂點後，這兩種方法都可以提供對樹的連通性的有用見解，並且適用於各種場景。

以上是從樹中刪除一個頂點後，查詢連通分量的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！