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

在本文中，我们将介绍如何使用C++从树中删除一个顶点后查询连通分量的数量。树是一种非常重要的数据结构，常用于描述层次关系和网络结构。树中的顶点和边可以代表对象和它们之间的关系。删除一个顶点可能会导致整个树的结构发生变化，因此需要重新计算连通分量的数量。下面我们将详细讨论这个问题，并给出相应的实现示例。

阅读更多：C++ 教程

连通分量

在开始之前，让我们先了解一下连通分量的概念。在一个图结构中，如果两个顶点之间存在路径，那么它们就是连通的。一个连通分量是指图中所有顶点和边的一个子集，其中任意两个顶点都是连通的，但是与其他连通分量中的顶点不连通。在树中，每一个顶点都是唯一与其他顶点连通的，所以树只有一个连通分量。

删除顶点后的连通分量查询算法

当我们从树中删除一个顶点后，树的结构可能会发生改变，原本与被删除顶点连通的子树会变成一个新的独立子树。为了查询删除之后的连通分量数量，我们可以使用深度优先搜索（DFS）算法。

首先，我们需要构建一个表示树的数据结构，并初始化连通分量数量为1。然后，从根节点开始进行深度优先搜索，访问与当前节点相邻的子节点，并将它们的父节点设置为当前节点。遍历树的过程中，我们可以将访问过的节点标记为已访问，并将连通分量数量加1。当遍历完成后，连通分量的数量就是我们要查询的结果。

接下来，我们给出一个使用C++实现的例子：

#include <iostream>
#include <vector>

using namespace std;

class TreeNode {
public:
    int val;
    vector<TreeNode*> children;

    TreeNode(int x) : val(x) {}
};

int countComponents(TreeNode* root) {
    int count = 0;
    if (root == nullptr) {
        return count;
    }
    vector<bool> visited(1001, false);
    dfs(root, visited, count);
    return count;
}

void dfs(TreeNode* node, vector<bool>& visited, int& count) {
    visited[node->val] = true;
    for (auto child : node->children) {
        if (!visited[child->val]) {
            dfs(child, visited, count);
        }
    }
    count++;
}

int main() {
    // 构建一个树的示例
    TreeNode* root = new TreeNode(1);
    TreeNode* node2 = new TreeNode(2);
    TreeNode* node3 = new TreeNode(3);
    TreeNode* node4 = new TreeNode(4);
    TreeNode* node5 = new TreeNode(5);

    root->children.push_back(node2);
    root->children.push_back(node3);
    node2->children.push_back(node4);
    node3->children.push_back(node5);

    int result = countComponents(root);
    cout << "连通分量的数量为：" << result << endl;

    return 0;
}

在上面的例子中，我们首先构建了一个树的示例，然后调用countComponents函数查询连通分量的数量，并将结果打印输出。运行程序后，输出结果为：