树的重心(dfs)
写的磕磕绊绊的
1.甚么是树的重心
gpt给的解释是:在树中,重心是指树中一个节点,如果将该节点从树中删除后,剩余部分中任意一颗子树的大小都不超过总节点数的一半,那么这个节点就是树的重心。也就是说,树的重心是使得子树最大值最小的节点。每棵树最多只有两个重心。
2.计算树的重心的常见算法是使用深度优先搜索(DFS)来遍历整棵树,同时记录每个节点的子树大小和总节点数,然后计算每个节点的最大子树大小,最后找出最小的最大子树大小对应的节点即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = N*2;//以有向图的格式存储无向图,所以每个节点至多对应2n-2条边
int n;//题目所给的输入 n个节点
int h[N]; //邻接表存储树,有n个节点
int e[M];//存储元素
int ne[M];//存储邻接表的next值
int idx;//单链表指针
bool st[N];//记录节点是否被访问过,访问过则标记为true
int ans = N;//最小重心的最大连通块的值
void add(int a ,int b)
{
e[idx] = b, ne[idx] = h[a] ,h[a] = idx++;
}
//返回以u为根的子树的大小
int dfs(int u)
{
int sum=1;//存储 以u为根的树 的节点数, 包括u,如图中的4号节点
int res = 0;//把重心删掉之后每一个连通块大小的最大值
st[u] = true;//标记一下,已经被搜过了
for (int i = h[u]; i != -1; i = ne[i] )
{
int j = e[i];
if(!st[j]) //因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
{
int s = dfs(j);//用s表示当前子树的大小
res = max(res , s);
sum += s;//s子树是以u为节点的子树的一部分
}
}
res = max(res , n-sum);//n-sum就是图示中的最大那一块
ans = min(res , ans);//最小重心的最大连通块的值
return sum;//返回以u为根的子树的大小
}
int main()
{
memset(h, -1 , sizeof h);//初始化h数组 -1表示尾节点
cin >> n;
// 题目接下来会输入,n-1行数据,
// 树中是不存在环的,对于有n个节点的树,必定是n-1条边
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;
}