資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究從樹中移除頂點後計算連通分量的查詢
可以使用以下查詢來確定刪除樹頂點後剩餘的連通分量的數量：首先考慮樹結構。然後，透過使用廣度優先或深度優先搜尋演算法遍歷樹，檢查每個連通分量。在刪除所需頂點後，使用相同的遍歷方法確定連通分量的數量。結果將由刪除前後的計數差異決定。此方法有效地監視連線變化並幫助計算更新後的樹中的連通分量。
使用的方法
深度優先搜尋 (DFS) 方法
並查集方法
深度優先搜尋 (DFS) 方法
在 DFS 方法中，我們首先從原始樹中的任何選定節點執行 DFS 遍歷，以計算刪除樹中的頂點後連通分量的數量。在此遍歷期間，我們遍歷每個連線的節點，將每個節點標記為已訪問，並跟蹤 DFS 的呼叫次數。在刪除指定頂點後，我們執行新的 DFS 遍歷，確保在探索階段跳過已刪除的頂點。透過比較刪除前後 DFS 呼叫的次數，我們可以確定更新後的樹中連通分量的數量。此方法有效地計算連通元素，同時調整樹結構的變化。
演算法
在原始樹上選擇任何頂點作為 DFS 遍歷的起點。
設定變數“count”以開始計數連通分量。最初將其設定為 0。
從選定的起始頂點開始，使用 DFS 遍歷樹。
標記在 DFS 遍歷期間訪問的每個頂點，併為每個新的 DFS 呼叫（即，為找到的每個連通分量）將“count”增加 1。
DFS 遍歷完成後，“count”將表示原始樹中連通元素的數量。
從樹中刪除指定的頂點。
從相同的起始頂點重複 DFS 遍歷，確保避免探索已刪除的頂點。
在執行 DFS 時，類似於之前更新“count”變數。
升級後的樹中關聯元件的數量將由從初始“count”中減去撤離後的“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 方法從選定的頂點開始遍歷，標記每個訪問的節點，並計算連通分量。刪除頂點後，執行新的遍歷而不包括已刪除的節點，並透過比較遍歷前後的計數獲得更新後的計數。
並查集方法透過將每個頂點初始化為單獨的元件來確定初始連通分量計數，並使用並查集操作。刪除頂點後，應用相同的並查集操作，並計算不同的父代表以獲得更新後的計數。
兩種方法在刪除頂點後都提供了對樹的連通性的有用見解，並且適用於各種場景。
160 次瀏覽
