从树中删除一个顶点后，查询连通分量的数量

以下查询可用于确定删除树顶点后剩余的连通分量：首先考虑树结构。然后，通过使用广度优先或深度优先搜索算法在树中移动，检查每个连接的组件。一旦所需的顶点被驱逐，就使用相同的遍历方法来决定连接组件的数量。结果将根据开除前后计数的变化来决定。该方法有效地监视连接变化并帮助计算更新树中的连接组件。

使用的方法

• 深度优先搜索 (DFS) 方法

• 并查法

深度优先搜索 (DFS) 方法

在 DFS 方法中，我们首先从原始树中的任何选定节点执行 DFS 遍历，以在从树中删除顶点后对连接的组件进行计数。在此遍历过程中，我们遍历每个连接的节点，将每个节点标记为已访问，并跟踪使用 DFS 的次数。我们在删除指定顶点后执行新的 DFS 遍历，确保在探索阶段跳过删除的顶点。我们可以通过比较删除前后调用 DFS 的次数来确定更新树中连通分量的数量。这种方法可以有效地计算连接元素的数量，同时根据树结构的变化进行调整。

算法

• 选取原树上的任意一个顶点作为DFS遍历的起点。

• 设置变量“count”以开始对连接的组件进行计数。首先，将其设置为 0。

• 从选定的起始顶点，使用 DFS 遍历树。

• 标记 DFS 遍历期间访问的每个顶点，并为每个新的 DFS 调用（即，对于找到的每个连接组件）将“计数”增加 1。

• DFS遍历完成后，原树中连通元素的数量将用“count”表示。

• 从树中删除指定的顶点。

• 从同一起始顶点重复 DFS 遍历，确保避免探索已删除的顶点。

• 在运行 DFS 时，与之前类似地更新“count”变量。

• 升级后的树中关联组件的数量将通过从开始的“计数”中减去疏散后的“计数”来确定。

示例

#include 
#include 

void dfs(const std::vector>& tree, int v, 
std::vector& 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>& tree, int startVertex) {
   int n = tree.size();
   std::vector visited(n, false);
   int count = 0;

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

int main() {
   std::vector> 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 
#include 

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 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 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 方法使用并集运算来确定的，该方法将每个顶点初始化为单独的组件。删除顶点后应用相同的并集操作，并对不同的父代表进行计数以获得更新的计数。

删除顶点后，这两种方法都可以提供对树的连通性的有用见解，并且适用于各种场景。

奇布塔

基于AI生成技术的一站式有声绘本创作平台

下载