首页 > Windows开发 > 详细

ACWing846. 树的重心

时间:2021-02-23 23:37:24      阅读:1      评论:0      收藏:0      [点我收藏+]

题目

分析

技术分享图片

 

 

DFS,一次遍历,求出每个结点去除该点后的最大连通块的个数,同时更新ans(全局变量存放最终结果)

代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int N = 100010;
 7 int h[N], e[N*2],ne[N*2],idx;//树为无向联通图,所以a->b,b->a
 8 bool st[N];//记录是否被访问过
 9 int ans = N;//保存最终结果
10 int n;//结点个数
11 
12 //邻接表加入一条a->b的边
13 void add(int a,int b){
14    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
15 
16 }
17 
18 //返回子节点个数
19 int dfs(int u){
20     st[u] = true;
21     int sum = 1,res = 0;//注意sum为1,本身也算作一个节点,若为0,则都为0,res存放该节点最大连通块个数
22     for(int i = h[u];i!=-1;i = ne[i]){
23         int j = e[i];
24         if(!st[j]){
25             int s = dfs(j);//u的子节点的个数
26             sum += s;//加上u本身
27             res = max(res,s);
28         }
29     }
30     res = max(res,n-sum);//找到删掉该节点后最大连通块的个数
31     ans = min(res,ans);//找最小的最大值
32     return sum;//返回子节点个数
33     
34 }
35 int main(){
36     cin>>n;
37     memset(h,-1,sizeof(h));
38     //树:n个结点n-1条边
39     for(int i = 0;i < n-1;i++){
40         int a,b;
41         cin>>a>>b;
42         add(a,b);
43         add(b,a);
44     }
45     dfs(1);//从第一个结点开始
46     printf("%d",ans);
47     return 0;
48 }

 

ACWing846. 树的重心

原文:https://www.cnblogs.com/fresh-coder/p/14437495.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号