树的重心
感觉这题把之前基础课学的很多知识都用起来了
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
//用链表结构存储每个点的边
int h[N]; //h[]用于存储每个点的头节点
int e[2*N]; //用于存储元素 因为是无向图 所以是双向边 应该乘2
int ne[2*N]; //存储链表的next值
int idx=0;
int n;
int ans=N; //记录重心子树的最小值
bool st[N]; //记录该点是否已经查找过
void add(int a,int b) //将b插入a中 a作为根 所以处在链表的最后
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u) //dfs过程寻找根的连通的点
{
int size=0; //存放连通块中点的个数的最大值
st[u]=true; // 该点已经走过
int sum=0; //sum用于记录根子树的个数
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
int s=dfs(j);
size=max(size,s);
sum+=s;
}
}
size=max(size,n-sum-1); //通过画图可得n-m 即总的节点-根的子树 即为剩余的连通节点值
//而size为当前为根的子树的个数 通过比较确认连通块中点的最大数
ans=min(ans,size);
return sum+1; //return sum+1 是因为sum初始化为0 而当前这个点即根也算是该连通块内的一点
}
int main()
{
memset(h,-1,sizeof h); //初始化h[]表 -1表示空
scanf("%d",&n);
for(int i=0;i<n-1;i++) //注意这里应该n-1,
{ //有些奇怪但是 仔细想想就明白 n是表示点的个数 而每行是输入两个点之间的边所以只需输入n-1行即可
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
为啥数组e的最大个数为2N?,不应该是2N*(N-1)吗?
为什么这个dfs不用回溯?
不请自来~因为树是联通的里面的每个点都会被当作重心去假设得出一个答案,然后答案如果有满足的话就在不断更新呀
因为树在大多数情况中只需要遍历一遍,所以回不回溯对所得答案并无影响。
主函数的for循环是因为题目给的是树,而树定义是当且仅当任何两个点之间仅有一条路径的图,所以只要是树就一定只有n-1条边。
所以买本参考书还是有必要的。虽然难看。:)