ACWing846. 树的重心

题目

分析

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 }

注意图的存储是从1开始的