AcWing 846. 树的重心
原题链接
简单
作者:
七十二时c
,
2024-04-08 17:09:04
,
所有人可见
,
阅读 2
题目描述
样例
算法1
时间复杂度为o(n + m)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
/*
本题要求:输出将重心删除后,剩余各个连通块中点数的最大值.
本题思路:对树中的每个点都求出:把这个点删掉之后,其余所有连通块的点数的最大值,以打擂台的方式求出其中最小的那一个.
*/
int h[N]; // head数组的下标代表这是几号边,值表示 与该节点相连接的边的idx
int e[M]; // e数组的下标为idx(idx的含义见下),值表示 相应的idx代表几号边
int ne[M]; // ne[2] = 1 ne数组的下标为idx = 2,值 = 1 表示 idx = 2 所对应的边的相邻边的idx
int idx; // 是一条边的唯一编号
int ans = N;// ans表示重心的所有的子树中,最大的子树的结点数目
int n;
bool st[N]; // 记录节点是否被访问过,访问过则标记为true
// 将a -> b || a所对应的单链表中插入b a作为根
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 返回以u为根的树中所有结点个数(存在变量sum中)
int dfs(int u)
{
int res = 0; //存储删掉某个节点之后,最大的连通子图 节点数
st[u] = true; // 表示u节点已经被遍历
int sum = 1; //sum表示以这一点为根结点的树中所有结点个数
for(int i = h[u];i != -1;i = ne[i])
{
int x = e[i];
if(!st[x])
{
int s = dfs(x);
res = max(s,res);
sum += s;
}
}
res = max(res,n - sum);
ans = min(res,ans);
return sum;
}
int main()
{
memset(h, -1, sizeof h); // 将h[]数组初始化成-1,-1表示空结点
cin >> n;
for(int i = 0; i < n;i++)
{
int a,b;
cin >> a >> b;
add(a, b),add(b, a); // 无向图
}
dfs(2); // 可以从图像中任意一个节点出发,遍历整个树(因为都是无向边)
cout << ans << endl;
return 0;
}