ACWing846. 树的重心

作者:神秘网友 发布时间:2021-02-23 17:20:13

ACWing846. 树的重心

题目

分析

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

代码

 1 #includeiostream
 2 #includealgorithm
 3 #includecstring
 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     cinn;
37     memset(h,-1,sizeof(h));
38     //树:n个结点n-1条边
39     for(int i = 0;i  n-1;i++){
40         int a,b;
41         cinab;
42         add(a,b);
43         add(b,a);
44     }
45     dfs(1);//从第一个结点开始
46     printf("%d",ans);
47     return 0;
48 }

ACWing846. 树的重心 相关文章

  1. 考研机试 7.质因数的个数

    时间:2021/02/23 一.题目描述 求正整数N(N1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。 输入描述 可能有多组测试数据,每组测试数据的输入是一个正整数N,(1N10^9)。 输出描述 对于每组数据,输出N的质因数的个数。 题

  2. 力扣刷题记录2021.2.23 一维数组的动态和

    题目描述 给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。 请返回 nums 的动态和。 示例 1: 输入:nums = [1,2,3,4] 输出:[1,3,6,10] 解释:动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。 示例 2: 输入:num

  3. 题解 P2365 任务安排

    题目描述 Link 给定 \(n\) 个任务,每个任务有两个属性: \(t_i\) 和 \(c_i\) ,分别表示这个任务的时间和花费。 现在你需要把原本的任务分成若干批(不能改变原本的顺序),机器可以一次执行完这些任务,在执行每一批任务之前,需要 \(s\) 的准备时间,然后

  4. 汉诺塔题解

    题目: 汉诺塔由三根柱子(分别用A、B、C表示)和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上,大的在下面,小的在上面,形成了一个塔状的锥形体。 对汉诺塔的一次合法的操作是指:从一根柱子的最上层拿一个盘子放到另一根柱子的最上层,同

  5. 875. 爱吃香蕉的珂珂

    875. 爱吃香蕉的珂珂 题目链接:875. 爱吃香蕉的珂珂 珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。 珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根

  6. 【LeetCode】1052. 爱生气的书店老板

    题目链接:https://leetcode-cn.com/problems/grumpy-bookstore-owner/ 本题使用前缀和 + 双指针解决 首先,假设: 书店老板强制冷静的时间段是 \([i, i + X - 1]\) 正常情况下,书店老板不抑制自己情绪最后收获的顾客满意度是 \(sum\) 正常情况下,在时间段

  7. 闭包题目

    //题目一 var name = "The Window"; var object = { name: "My Object", getNameFunc: function () { return function () { return this.name; }; } }; console.log(object.getNameFunc()()); //直接调用,默认调用对象是window 答案:the window 题目二: /

  8. 【剑指offer】变态跳台阶 --Java实现

    题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入 3 返回值 4 思路分析 设跳到第n阶的跳法共有f(n)种 假设现在已经跳到了第n阶,那么前一步跳到哪里了呢 如果前一步跳一步到了

  9. 【luogu P3806】【模板】点分治1

    【模板】点分治1 题目链接:luogu P3806 题目大意 给你一棵树,路径有长度,多次询问,每次给出 k,问你是否存在路径长度为 k 的点对。 思路 这道题我们用分治的方法。 那我们假设要解决一个树,那我们先选重心作为根节点(为了减少高度节省时间)。 然后就

  10. 1052. 爱生气的书店老板(滑动窗口)

    一、题目描述 今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。 在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 gr

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词