AcWing 846. 树的重心
原题链接
简单
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ans=N;//记录最小的最大值 所以初始化成一个大于所有连通块数的值N
int n;//全局变量 方便dfs中计算第u个结点"上面"的连通块的个数
//采用邻接表存储图
int h[N],v[2*N],ne[2*N],idx;
bool flag[N];//标志数组 判断dfs过程中某个结点是否被访问过
//插入边
void add(int a,int b)
{
v[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//u表示当前是第u个结点
int dfs(int u)//返回值是以u为根的子树中结点的个数
{
//标志数组中更改第u个结点的状态
flag[u]=true;
//res记录的是将u这个点删除后 剩余各个连通块中点数的最大值
int res=0,sum=1;//sum记录的是以u为根的子树中结点的个数
for(int i=h[u];i!=-1;i=ne[i])
{
int j=v[i];
if(flag[j]) continue;//如果当前结点已经被访问过 则直接进入下一次循环
int size_j=dfs(j);//以j为根的子树中结点的个数
sum+=size_j;
res=max(res,size_j);//取剩余各个连通块中点数的最大值
}
//sum计算完成 用来计算第u个结点"上面"的连通块的个数
res=max(res,n-sum);//第u个结点"上面"的连通块的个数=n-sum
ans=min(ans,res);
return sum;//返回值是以u为根的子树中结点的个数 也就是这里sum的值
}
int main()
{
scanf("%d",&n);
//初始化h数组为-1 表示里面都是空结点
memset(h,-1,sizeof(h));
for(int i=0;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);//因为是无向边 所以a b添加一次 b a添加一次
}
//注意这里的参数范围为1~n之间
dfs(1);//无论那个结点都可以 因为dfs都会遍历完成整个树
cout<<ans<<endl;
return 0;
}