acwing 846. 树的重心

这篇具有很好参考价值的文章主要介绍了acwing 846. 树的重心。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。

请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

输入格式
第一行包含整数 n,表示树的结点数。

接下来 n−1 行,每行包含两个整数 a 和 b,表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m,表示将重心删除后,剩余各个连通块中点数的最大值。

数据范围
1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例:
4


先画出题目给出的树:
acwing 846. 树的重心


解释一下什么是树的重心
树的重心是指,删除某个结点后剩下的最大连通子树的结点数目最小,如上图是根据样列生成的树

若删除结点1,则剩下三个子树最大的是中间那颗结点有4个,即剩下的最大连通子树的结点数目为4;
若删除结点2,则剩下两个数目为1的子树和一个数目为6的子树,即剩下的最大连通子树的结点数目为6;
若删除结点3,剩下一个数目为1的子树,和一个数目为7的子树,即剩下的最大连通子树的结点数目为7……
枚举可得剩下的最小的最大连通子树的结点数目为4也就是说结点1是树的重心。另外注意题目要求答案是输出剩下的最小的最大连通子树的结点数目。

思路:树的深搜

算出每个结点被删除后剩下的最大连通子树的结点数目,输出最小值即可,那么问题就是怎么求一个结点被删除后的最大连通子树的结点数目,删除一个结点后,剩下的子树可以被分为两个部分,例如删除结点4:

acwing 846. 树的重心
蓝色部分是结点4的子树,红色部分我们暂时称为其他部门,因为我们知道树的总结点数n,只要能算出蓝色部分的数目s,那么其他部分的数目就是n-s

代码如何实现

一是这颗树我们要怎么存储,
二是上述dfs怎么实现

树的存储

首先树是一种特殊的图(无向图),存储图有邻接矩阵法和邻接表法,这里选择邻接表法,另外这里的是无向图,所以存边的时候要存正反两条。

acwing 846. 树的重心
存储代码实现:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入,n个节点

//a所对应的单链表中插入b  a作为根 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}
  
int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin >> n; //表示树的结点数

    // 题目接下来会输入,n-1行数据,
    // 树中是不存在环的,对于有n个节点的树,必定是n-1条边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }
    
    // 打印邻接表
    for(int i =1; i <= n ; i ++)
    {
        cout << i << ": ";
        for(int j = h[i]; j != -1; j = ne[j])
            cout << "->" << e[j];
        cout << endl;
    }

    return 0;
}

原始无向图:

acwing 846. 树的重心

运行结果:
acwing 846. 树的重心

最后dfs 是怎么实现的,只需要在深搜中统计当前节点子树的个数,然后判断出最小的最大连通子树节点数目

如图:可以按照题目意思,求出每个点删除后的最大值是多少, 然后求这些最大值中的最小值
acwing 846. 树的重心

在树的深度优先遍历中,可以求出每个子树的点的数量的

code:文章来源地址https://www.toymoban.com/news/detail-414141.html

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图,所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入,n个节点
int ans = N; //表示重心的所有的子树中,最大的子树的结点数目

bool st[N]; //记录节点是否被访问过,访问过则标记为true

//a所对应的单链表中插入b  a作为根 
//将b插入a中 a作为根 所以处在链表的最后
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// dfs 框架
/*
void dfs(int u){
    st[u]=true; // 标记一下,记录为已经被搜索过了,下面进行搜索过程
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) {
            dfs(j);
        }
    }
}
*/

//返回以u为根的子树中节点的个数,包括u节点
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后,最大的连通子图节点数
    st[u] = true; //标记访问过u节点

	// sum用于记录根子树的个数
    int sum = 1; //存储 以u为根的树 的节点数, 包括u,如图中的4号节点

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数
        }
    }

    //n-sum 如图中的n-size值,不包括根节点4;
    res = max(res, n - sum); // 选择u节点为重心,最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中,最小的最大联通子图的 节点数
    return sum;
}

int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin >> n; //表示树的结点数

    // 题目接下来会输入,n-1行数据,
    // 树中是不存在环的,对于有n个节点的树,必定是n-1条边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }

    dfs(1); //可以任意选定一个节点开始 u<=n

    cout << ans << endl;

    return 0;
}

到了这里,关于acwing 846. 树的重心的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 863. 二叉树中所有距离为 K 的结点

    863. 二叉树中所有距离为 K 的结点 C代码:dfs

    2024年02月09日
    浏览(35)
  • 【图论C++】树的重心——教父POJ 3107(链式前向星的使用)

    UpData Log👆 2023.9.26 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述是个人理解,可能不够标准,但能达其意 树 是 图 的一种 特例 , 树 就是 “没有环” 的 连通图 判断一个 图 是否是一个 树 ,需要满足的条件: 1)树根 :一棵树可以基于 无向图 与 有向图 ,区别在

    2024年02月07日
    浏览(44)
  • leetcode 572. 另一颗树的子树

    这道题重在思路,默认大家会判断两个树是否完全相同 我会把一些基础的简单的(包括  判断两个树是否完全相同   和之前的 求结点个数 )单独出博客,或者放在介绍堆和树的知识点里面 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值

    2024年02月04日
    浏览(33)
  • 在二叉树中查找值为 x的结点,试编写算法(用 C语言)打印值为 X 的结点的所有祖先,假设值为x的结点不多于一个。

    分析: 两种思路,递归和非递归。 思路: 考虑递归,当前结点值不等于 x 时,递归其左右子树,如果两者有一个返回值为 true,则说明当前结点为 x 的祖先结点,直接打印。 思路: 非递归,因为在遇到 x 的时候需要将其所有祖先打印,而当访问到 x 且能保留x 的祖先的方法

    2024年02月03日
    浏览(41)
  • 【Leetcode】相同的树、对称二叉树、另一颗树的子树

    目录 💡相同的树 题目描述 思路: 代码: 💡对称二叉树 题目描述 思路: 代码: 💡另一棵树的子树 题目描述 思路: 代码: 💡总结   给你两棵二叉树的根节点  p  和  q  ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则

    2024年02月04日
    浏览(42)
  • 假设二叉树中每个结点值为单个字符,采用二叉链存储结构存储。设计一个算法,求二叉树b中第k层上叶子结点个数(非递归算法)。

    int LevelCount(BiTNode *b,int k){         BiTNode *p=b,*temp[Maxsize];         int layer=0,count=0, m=0, n=1; (m: 上一层结点的尾   n: 当层结点的尾 )         temp[0]=NULL;         temp[1]=p;         if(p==NULL) return 0;// 二叉树为空,任意层结点个数均为 0         while(1){          

    2024年02月04日
    浏览(50)
  • 2942. 查找包含给定字符的单词【简单】

    给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。 请你返回一个 下标数组 ,表示下标在数组中对应的单词包含字符 x 。 注意 :返回的数组可以是 任意 顺序 示例 1: 示例 2: 示例 3: 提示 1 = words.length = 50 1 = words[i].length = 50 x 是一个小写英文字母 words[i] 只包含小写

    2024年02月19日
    浏览(38)
  • 递归求二叉树的结点总数及叶子结点总数

    有的方法中将左右子树分别进行计算,需要使用到两个变量;若使用全局变量,在对多个二叉树计算节点数时结果会进行累计,不易观察,使用一个全局变量就很方便。 结点总数=根结点数+左子树结点数+右结点数;判断根结点不为空,count++,然后再加上左右子树的个数。 这

    2024年02月04日
    浏览(43)
  • Java解决查找包含给定字符的单词

    给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。 请你返回一个 下标数组 ,表示下标在数组中对应的单词包含字符 x 。 注意 ,返回的数组可以是 任意 顺序。 示例 1: 示例 2: 示例 3: 提示: 1 = words.length = 50 1 = words[i].length = 50 x 是一个小写英文字母。 words[i] 只包

    2024年02月20日
    浏览(29)
  • 题目:2185.统计包含给定前缀的字符串

    ​​ 题目来源:         leetcode题目,网址:2185. 统计包含给定前缀的字符串 - 力扣(LeetCode) 解题思路:        遍历判断即可。 解题代码: 总结:         官方题解也是一样的思路。

    2024年02月15日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包