树与图深度优先遍历——acwing

题目一：树的重心

846. 树的重心 - AcWing题库

 

分析

采用暴力枚举，试探每个点，除去之后，连通分量最大值是多少， 各个点的最大值找最小的

因为可以通过 dfs 来得到 根u以下点数，以及可以求各分树的点数，

所以采用 邻接表存储数据的方式。

vis 标记搜索

需要存 最终答案 ans

需要存每个顶点及其以下点数 sum ， 需要存每个顶点子树 res

代码 

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10, M = 2*N;int h[N], e[M], ne[M], idx;
int n;
int ans = N; bool vis[N];
// 前插法将b插入a链表
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 以u为根子树的点的大小
int dfs(int u) {vis[u] = true; // 搜索int sum = 1, res = 0; // 以u为，根子树大小， ans 为除去根for(int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if(!vis[j]) {int s = dfs(j);res = max(res,s); // 该根多个子树的最大值sum += s; // 该根往下的总和}}res = max(res,n-sum); // 该根往下最大值，以及 剩下的比较ans = min(ans,res); //求到了除去u连通分量点最大值， 更新暴力枚举中每个u的最小值。return sum;//往上返回点数
}int main() {memset(h,-1,sizeof h);cin >> n;for(int i = 0; i < n-1; i ++) {int a, b;cin >> a >> b;add(a,b), add(b,a); // 搭建无向图}dfs(1);//都是可以相通的，随便dfs一个顶点cout << ans << endl;return 0;
}