算法刷题笔记 树的重心（树的优先遍历，C++实现）

题目描述

• 给定一颗树，树中包含n个结点（编号1∼n）和n−1条无向边。
• 请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
• 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

• 第一行包含整数n，表示树的结点数。
• 接下来n−1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

输出格式

• 输出一个整数m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

• 1 ≤ n ≤ 10^5

基本思路

• 本题仍然采用树的深度优先搜索算法进行实现。
• 每次移除树中的一个点，可以将树分为多个部分，分别是树的多棵子树和一个连通块。只需要比较这些子树和连通块的大小即可。

实现代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// 输入的树的结点个数
int n;

const int N = 100010;
vector<int> adjacent_table[N];   // 充当邻接表的向量数组
bool visited[N];                 // 判定结点是否遍历过的数组
int tree_size[N];                // 以每一个结点作为根节点的子树大小
int result = N ;                 // 记录最终的返回结果

// 基于深度优先搜索算法的函数
void dfs_search(int current)
{
    // 标记当前结点，表示其已经被遍历过
    visited[current] = true;
    // 将初始的子树大小设置为1（只有自己）
    tree_size[current] = 1;
    
    // 通过邻接表找到当前结点的所有子结点，递归地计算这些子节点的子树规模
    int max_treesize = 0;
    for(int child : adjacent_table[current])
    {
        // 如果当前的子节点还没有被访问过的情况
        if(visited[child] == false)
        {
            // 递归地通过深度优先搜索对其进行访问
            dfs_search(child);
            // 修改当前结点的子树规模
            tree_size[current] += tree_size[child];
            // 比较当前子树规模和该结点当前的最大子树规模
            max_treesize = max(max_treesize, tree_size[child]);
        }
    }
    // 修改当前时刻的结果
    result = min(max(max_treesize, n - tree_size[current]), result);
}

int main(void)
{
    // 输入树的结点个数
    scanf("%d", &n);
    // 输入每一条边，注意点的下标从1开始且是双向边
    for(int i = 0; i < n - 1; ++ i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        adjacent_table[a].push_back(b);
        adjacent_table[b].push_back(a);
    }
    // 通过深度优先搜索算法函数获取最终结果
    dfs_search(1);
    // 输出最终结果
    printf("%d", result);
    return 0;
}