题目描述
样例
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N],e[2*N],ne[2*N],idx;
bool st[N]; int ans = N;
int n;
void add(int a,int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u){
st[u] = true;//该节点被遍历
int res = 0; //求以删除该节点的子树中最大连通树的节点。
int sum = 1; //记录当前子树的节点个数
for(int i = h[u]; i != -1; i = ne[i]){ //遍历邻接表
int j = e[i]; //取邻接表中的节点
if(!st[j]){
int s = dfs(j); //求其中一颗子树节点的个数
//与自己的子树节点比较
res = max(res,s); //求该节点的最大连通树的节点数量 这里 1,2过程陆续与res比较
sum += s; //保留当前树的节点数量 这里 1+2+3
}
}
//与所有节点比较
//1.先于除自己和子树节点的其他节点比较求最大 就是 1+2+3 与 4 比较
res = max(res,n-sum);
//2.与删除其他中心点的最大连通树进行比较求最小
ans = min(ans,res);
return sum;
}
int main(){
scanf("%d",&n);
int a,b;
memset(h,-1,sizeof h);
for(int i = 0; i < n; i++) {
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1); //因为是无向图,可以从任意一节点开始
printf("%d",ans);
return 0;
}
我的金轮!
我太捞了
太细了,看了这么多的题解,唯一完全看懂的。主要是结合图像来讲解,非常清楚。
搞得不丑
金轮嘿嘿我的金轮
感谢
很强 点赞支持
太细了,太细了,学习到了很多
传入1 求1为根的子树中节点的个数 然后开始访问其子节点 那么在访问子节点的时候把当前节点标记为True 再次访问的时候 比如现在是求2为根的子树中节点的个数 那么不就无法访问了吗 状态已经被设置成访问过了 就无法求2为根的子树中的节点的个数了不是嘛 想不明白这个点头大 望指教
遍历的时候每个结点只能被访问一次。但是存无向图的时候需要把1->2和2-1这两条边都存入邻接表里。为了避免一个点多次遍历,需要设立判重数组。如你所说的当前1号结点被设置为true,当进入到2时,2就不能往回走到1了,因为1已经设为TRUE,就避免了多次访问1。计算以2为根的子树此时是不包括1结点的。所以不影响。
有点东西的基隆!
雀氏细
请问还是不太理解最后为什么要返回sum 有什么用么?
返回的sum是以u为根节点的树的大小
嗯嗯,现在懂了,感谢感谢!
太烧了,金轮