算法刷题笔记 树的重心（树的优先遍历，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;
}