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