AcWing 846. 树的重心
原题链接
简单
作者:
墨白
,
2021-01-05 16:46:45
,
所有人可见
,
阅读 301
C++ 代码
#include <iostream>
#include <algorithm>
//使用到单链表都需要这个头文件
#include <cstring>
using namespace std;
const int N = 100010 , M = N*2;
int n;
int result = N;
int idx;
//用于模拟链表的数组
int h[N];
int e[M];
int ne[M];
bool st[N];
void addNode(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int u){
st[u] = true;
int res = 0,sum = 1;
//从头节点开始找,找该节点的所有子节点
for(int i = h[u]; i != -1;i = ne[i]){
int j = e[i];
if(!st[j]){
int m = dfs(j);
//找到所有孩子节点中最大的
res = max(m,res);
sum += m;
}
}
//比较这个节点所有孩子中最大的和其他连通域的大小
res = max(res,n - sum);
result = min(result,res);
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;
addNode(a,b);
addNode(b,a);
}
dfs(1);
cout << result <<endl;
return 0;
}