题目描述
给定一颗树,树中包含 $n$ 个结点(编号 $1∼n$)和 $n−1$ 条无向边。
请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
输入格式
第一行包含整数 $n$,表示树的结点数。
接下来 $n−1$ 行,每行包含两个整数 $a$ 和 $b$,表示点 $a$ 和点 $b$ 之间存在一条边。
输出格式
输出一个整数 $m$,表示将重心删除后,剩余各个连通块中点数的最大值。
数据范围
$1≤n≤105$
样例
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例:
4
算法
深度优先搜索
时间复杂度
$O(n+m)$
参考文献
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
// N表示结点数, M表示边数(因为是无向图, 转换成有向图后 最大边数是结点数的2倍)
const int N = 100010, M = N*2;
int n;
// 使用邻接表存储图
// h[N] 存储邻接表头
// 需要说明: idx 表示当前使用的边 (而在邻接表中idx表示当前使用的结点)
// e[i] 存储第i条边指向的结点
// ne[i] 存储的是下一条边
// 即使用邻接表存储图时, 邻接表中的结点其实表示的是边
int h[N], e[M], ne[M], idx;
// 在图中 无论是dfs还是bfs每个结点都只遍历一次, 因此st[N]用来存储结点是否遍历
bool st[N];
// ans 存储删除某个结点后 最大剩余点数最小的 连通块 的点数(相当于重心)
int ans = N;
// 在 a结点 和 b结点之间添加一条边
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
// 返回以u为根的子树中点的数量
// 使用dfs
int dfs(int u)
{
st[u] = true; //标记一下, 当前的点已经被搜索过了
int sum = 1; // 当前子树大小, 从1开始
int res = 0; // 把u删除后, 每一个连通块中点数的最大值
// // 树和图的深度优先搜索
// // i表示边
// for (int i=h[u]; i != -1; i=ne[i])
// {
// int j = e[i]; // 图中的结点(树的结点)
// if (!st[j]) dfs(j);
// }
// i表示边
for (int i=h[u]; i != -1; i=ne[i])
{
int j = e[i]; // 图中的结点(树的结点)
if (!st[j])
{
int s = dfs(j); // 以j为根的子树大小
res = max(res, s); // 以j为根的子树也是一个连通块(把u删除后), 因此更新res
sum += s; // 以j为根的子树也是 以u为根的子树的一部分, sum为以u为根的子树大小, 因此更新sum
}
}
res = max(res, n-sum); // n-sum 表示在该树中, 处理以u为根的子树外其余的部分的点的数量(这个其余的部分也是一个连通块)
ans = min(ans, res);
// 返回以u为根的子树大小
return sum;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i=0; i<n-1; i++)
{
int a, b;
cin>>a>>b;
add(a, b);
add(b, a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}