1.树的重心 acwing 846
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 5 using namespace std; 6 7 const int N = 1e5 + 10; //数据范围是10的5次方 8 const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边 9 10 int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点 11 int e[M]; //存储元素 12 int ne[M]; //存储列表的next值 13 int idx; //单链表指针 14 int n; //题目所给的输入，n个节点 15 int ans = N; //表示重心的所有的子树中，最大的子树的结点数目 16 17 bool st[N]; //记录节点是否被访问过，访问过则标记为true 18 19 //a所对应的单链表中插入b a作为根 20 void add(int a, int b) { 21 e[idx] = b, ne[idx] = h[a], h[a] = idx++; 22 } 23 24 // dfs 框架 25 /* 26 void dfs(int u){ 27 st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程 28 for(int i=h[u];i!=-1;i=ne[i]){ 29 int j=e[i]; 30 if(!st[j]) { 31 dfs(j); 32 } 33 } 34 } 35 */ 36 37 //返回以u为根的子树中节点的个数，包括u节点 38 int dfs(int u) { 39 int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数 40 st[u] = true; //标记访问过u节点 41 int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点 42 43 //访问u的每个子节点 44 for (int i = h[u]; i != -1; i = ne[i]) { 45 int j = e[i]; 46 //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过 47 if (!st[j]) { 48 int s = dfs(j); // u节点的单棵子树节点数 如图中的size值 49 res = max(res, s); // 记录最大联通子图的节点数 50 sum += s; //以j为根的树 的节点数 51 } 52 } 53 54 //n-sum 如图中的n-size值，不包括根节点4； 55 res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数 56 ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数 57 return sum; 58 } 59 60 int main() { 61 memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点 62 cin >> n; //表示树的结点数 63 64 // 题目接下来会输入，n-1行数据， 65 // 树中是不存在环的，对于有n个节点的树，必定是n-1条边 66 for (int i = 0; i < n - 1; i++) { 67 int a, b; 68 cin >> a >> b; 69 add(a, b), add(b, a); //无向图 70 } 71 72 dfs(1); //可以任意选定一个节点开始 u<=n 73 74 cout << ans << endl; 75 76 return 0; 77 }