【图论C++】树的重心——教父POJ 3107(链式前向星的使用)
》》》算法竞赛
/*** @file * @author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * @brief 一直在竞赛算法学习的路上* * @copyright 2023.9* @COPYRIGHT 原创技术笔记:转载需获得博主本人同意,且需标明转载源* @language C++* @Version 1.0还在学习中 */
- UpData Log👆 2023.9.26 更新进行中
- Statement0🥇 一起进步
- Statement1💯 有些描述是个人理解,可能不够标准,但能达其意
技术提升站点
文章目录
- 》》》算法竞赛
- 技术提升站点
- 21 树上问题
- 21-0 关于 树 的问题 有哪些?
- 21-1 树的重心
- 21-1-1 重心是什么?
- 21-1-2 重心的性质
- 21-1-2 重心的查找
- 教父(poj 3107)
21 树上问题
树
是图
的一种特例,树
就是 “没有环” 的连通图
判断一个 图
是否是一个 树
,需要满足的条件:
-
1)树根:一棵树可以基于
无向图
与有向图
,区别在于树根。基于无向图的树(无根树),是没有固定树根的(也就是说树根的个数可能不止为1,或说每个结点都能做为树根)
基于有向图的树(有根树),有且仅有一个树根
-
2)父节点与子节点的关系:每个节点有且仅有一个父节点。从根节点遍历,必须由父节点遍历到子节点
-
3)连通性:从 根 出发可以遍历树上所有(除根节点外)节点,且到这些节点的路径只有一条
有根树 与 有向无环图 DAG 的 区别
有向无环图:不能从某点开始经过数点回到该点
有根树
都是 DAG
,DAG
不一定是 有根树
(如下图:虽然没有构成环,但是4号节点同时拥有两个父节点,不符合有根树的定义)
21-0 关于 树 的问题 有哪些?
直通车:
- 树的判断:判定 图 是否为 树 的方法是 DFS遍历
- 树的存储:与 图 的存储方式一致(链式前向星)
- 树的路径问题(包含了 查找最近公共祖先
LCA
):点击直通 树的路径问题 - 树的直径
- 树的重心(下文将讲解)
- 多叉树、二叉树
- 树上前缀和,树上差分
21-1 树的重心
21-1-1 重心是什么?
树的重心
适用在无根树(一个不含回路的无向图)
树的重心
是 以任意结点 u 为根 计算它最大子树的节点数 n o d e n node_n noden,如果u节点
的 n o d e n node_n noden 最少,则u节点
为 树的重心。
可以一眼看出:4号结点 就是 树的重心,因为这个点能满足 n o d e n node_n noden 是最小的(左子树{4,2,1,3,}:4个,右子树{4,5,6,7}:4个),而其他任意一个节点的子树(例如 2号节点的最大子树{2,4,5,6,7}5个)都是比这个点的最大子树的节点数是大的。
21-1-2 重心的性质
- 以树的重心为根时,所有子树的大小都不超过整棵树大小的一半。(树上分治会用到)

- 树的重心如果不唯一,则至多有两个,且这两个重心相邻。

- 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么到它们的距离和一样。

- 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上。

- 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。(往树上增加或减少一个叶子,如果原节点数是奇数,那么重心可能增加一个,原重心仍是重心;如果原节点数是偶数,重心可能减少一个,另一个重心仍是重心)
21-1-2 重心的查找
教父(poj 3107)
问题描述
城里有一个黑手党组织。把黑手党的人员关系用一棵树来描述,教父是树的根,每个节点是一个组织成员。为了保密,每人只和他的父节点和他的子节点联系。警察知道哪些人互相来往,但是不知他们的关系。警察想找出谁是教父。
警察假设教父是一个聪明人:教父懂得制衡手下的权力,所以他直属的几个小头目,每个人的属下的人数差不多。也就是说,删除根之后,剩下几棵互不连通的子树(连通块),其中最大的连通块应该尽可能小。请帮助警察找到哪些人可能是教父。
输入:第1行输入n,表示组织人数, 2 ≤ n ≤ 50000 2\leq n \leq 50000 2≤n≤50000 。组织成员的编号为1~n。下面n-1行中,每行输入两个整数,即有联系的两个人的编号。
输出:输出疑似教父的节点编号,从小到大输出。Input
6 1 2 2 3 2 5 3 4 3 6
Output
2 3
- 分析
“删除根之后,剩下几棵互不连通的子树(连通块),其中最大的连通块应该尽可能小”,这句话说明了 教父 就是 这个关系树里的 重心
如何计算以 u节点 为根的子树的结点
u节点 DFS 直到“碰壁”后,将栈里的数据依次弹出,弹出一个结点数加1。
那么这样的话,可以对删除根之后,剩下几棵互不连通的子树(连通块) 进行单独的DFS,对整棵树逐一删除节点,重复上述步骤,就能得到每个结点的最大连同块。
如何优化?
上面提出的方案是 使用 暴力法 解决,其实无需如此,可以依照线段树
的思维,对 同父节点的子节点 进行合并,得到父节点的子树的节点数,这样一次DFS就可以解决问题。
如上图,假如删除 结点1,得到3个连通块(含结点1的邻居:节点3、含结点1的邻居:节点0、含结点1的邻居:节点4)
对任意点做一次 DFS,特殊点,以 结点2为根节点 做DFS:
从2向0方向 一直DFS,直到遍历到节点10,停止遍历,栈开始弹出数据。,当弹出结点10时,记录 结点10 的度(即子树的结点数) D e g r e e [ 10 ] = 1 Degree[10]=1 Degree[10]=1,同理 D e g r e e [ 9 ] = 1 Degree[9]=1 Degree[9]=1;当弹出4时, D e g r e e [ 4 ] = D e g r e e [ 9 ] + D e g r e e [ 10 ] + 1 = 3 Degree[4]=Degree[9]+Degree[10]+1=3 Degree[4]=Degree[9]+Degree[10]+1=3,同理算出 D e g r e e [ 3 ] = D e g r e e [ 7 ] + D e g r e e [ 8 ] + 1 = 3 Degree[3]=Degree[7]+Degree[8]+1=3 Degree[3]=Degree[7]+Degree[8]+1=3;在弹出1时, D e g r e e [ 1 ] = D e g r e e [ 3 ] + D e g r e e [ 4 ] + 1 = 7 Degree[1]=Degree[3]+Degree[4]+1=7 Degree[1]=Degree[3]+Degree[4]+1=7;删除1后, D e g r e e [ 0 ] = n − D e g r e e [ 1 ] Degree[0]=n-Degree[1] Degree[0]=n−Degree[1]
存储:链式前向星
链式前向星
较领接矩阵
(二维数组)在空间上优化了很多
点击直通 链式前向星(图(树)的存储)
- 代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
vector<int> head(N,-1);
struct Edge{int to,next;Edge():to(-1), next(-1){} //初始化为无邻居节点
} edge[N<<1];
vector<int> Degree(N,1); //初始化每个节点的度(子树的结点数)为1
int edge_n=0; //记录边数
int GodFather_n=0; //记录可能得教父个数
int n; //人有n个,关系有n-1条
int MAX_Degree=1e9;
vector<int> ans(N,0);
void Add_Edge(int u, int v){edge[edge_n].to=v;edge[edge_n].next=head[u]; //记录 上一个邻居节点 的 存储编号head[u]=edge_n++; //当前 邻居节点 的 存储编号,以便下一个邻居节点的访问
}
void DFS(int u=1, int father=0){/*计算 cur结点 的 最大连通块的结点数*/int temp=0;for(int i=head[u]; ~i; i=edge[i].next){ //遍历cur节点的邻居节点[~i相当于i=-1]int v=edge[i].to; //v 是 u 的子节点if(v==father) continue;DFS(v,u); //DFS子树Degree[u]+=Degree[v]; //更新父节点的度temp=max(temp, Degree[v]); //记录cur结点的 最大子树 的 结点数}temp=max(temp, n-Degree[u]); //temp是cur最大连通块的节点数/*查找 结点数 最小的 最大连通块*/if(temp<MAX_Degree){ //满足条件的话,则temp是 疑似教父 的最大连通块的结点数MAX_Degree=temp; //更新 最小的 最大连通块GodFather_n=0; //找到新的最小,将它放在第一个ans[++GodFather_n]=u;}else if(temp==MAX_Degree)ans[++GodFather_n]=u;
}int main(int* argc, void* argv[]){cin>>n;for(int i=1; i<n;i++){int u,v; cin>> u >> v;Add_Edge(u,v); Add_Edge(v,u); //无向 记录 双向有向}DFS();sort(ans.data()+1, ans.data()+1+GodFather_n); //升序排列for(int i=1; i<=GodFather_n; i++)cout<<ans[i]<<" ";return 0;
}
相关文章:

【图论C++】树的重心——教父POJ 3107(链式前向星的使用)
》》》算法竞赛 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记:转载…...

hhh百度地铁广告太搞笑了;24家国内大模型公司面经;LLM法律应用实践;AI+教育产品图谱与工作流 | ShowMeAI日报
👀日报&周刊合集 | 🎡生产力工具与行业应用大全 | 🧡 点赞关注评论拜托啦! 🔥 会玩儿!承包地铁专列,真人移动广告 | 百度世界大会预热 百度也是会玩儿!承包了北京地铁一号线的「…...

项目管理:项目经理一定要避开这四大误区
项目经理要保质保量按时达成项目目标,需要关注项目的方方面面,要具有很强的沟通协调能力和目标意识。但是项目经理也不免不了失误,管理中的这四大误区,你经历过几个? 误区一:做不该做的事 你是否遇到这种…...

爬虫为什么需要 HTTP 代理 IP?
前言 爬虫在互联网数据采集、分析和挖掘中扮演着至关重要的角色,但是对于目标网站而言,频繁的爬虫请求可能会对其服务器产生不小的负担,严重的情况甚至会导致网站崩溃或者访问受限。为了避免这种情况的发生,同时也为了保护客户端…...
leetcode刷题笔记/代码随想录笔记——移除字符串中多余空格
1. 使用erase()函数 void removeExtraSpaces(string& s) {for (int i s.size() - 1; i > 0; i--) {if (s[i] s[i - 1] && s[i] ) {s.erase(s.begin() i);}}// 删除字符串最后面的空格if (s.size() > 0 && s[s.size() - 1] ) {s.erase(s.begi…...

dataGrip导出导入的方式
导出:选中需要导出的表 导入:选中导出的sql文件...
LeetCode279. 完全平方数
279. 完全平方数 文章目录 [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)一、题目二、题解方法一:完全背包二维数组方法二:一维数组(空间复杂度更小的改进版本,最下面的两个版本不需要存储完全平方数) 一、题…...
【CMake】add_dependencies 命令
【CMake】add_dependencies 原文链接:https://blog.csdn.net/new9232/article/details/125831009 参考链接:https://blog.csdn.net/new9232/article/details/121374943 简介 add_dependencies(<target> [<target-dependency>]...)官方文档…...

go语言unsafe.Pointer与uintptr
以下内容来源go语言圣经 1、unsafe.Pointer,相当于c语言中的void *类型的指针,如果需要运算需要转成uintptr类型的指针 2. uintptr uintptr是一个无符号的整型,它可以保存一个指针地址。 它可以进行指针运算。 uintptr无法持有对象, GC不把…...
ddos打到高防cdn上会发生什么
ddos打到cdn上会发生什么?当DDoS攻击打到CDN上时,肯定会影响网站的可用性和用户体验。具体DDoS攻击打到CDN上时,会发生以下情况: CDN节点负载增加:DDoS攻击会导致大量的无效流量涌入CDN节点,从而使得节点负载增加。这…...
【单调栈】503. 下一个更大元素 II
503. 下一个更大元素 II 解题思路 参考496. 下一个更大元素 I 首先计算nums2的每一个元素的下一个比他大的元素,使用单调栈 将上面的结果和nums2中的每一个元素组成映射map 针对每一个Nums1的元素 查询map 记录map 的value 但是这个是循环的数组元素 class So…...
C++ decltype类型
文章目录 1. 工作原理2. decltype 变量3. decltype 表达式4. decltype 函数 1. 工作原理 随着程序越来越复杂,程序中用到的类型也越来越多,我们有时候不得不去翻阅大量上下文去寻找此数据的类型。 decltype就是一种类型说明符,它的出现…...
【题解】JZOJ3854 分组
JZOJ 3854 题意 有 n n n 个人,每个人有地位 r i r_i ri 和年龄 a i a_i ai,对于一个若干人组成的小组,定义其队长为地位最高的成员(若相等则取二者均可),其他成员的年龄与队长的差不能超过 k k …...

区块链实验室(26) - 区块链期刊Blockchain: Research and Applications
Elsevier出版物“Blockchain: Research and Applications”是浙江大学编审的期刊。该期刊自2020年创刊,并出版第1卷。每年出版4期,最新期是第4卷第3期(2023年9月)。 目前没有官方的IF,Elsevier的引用因子Citescore是6.4。 虽然是新刊…...
【学习笔记】[ARC153F] Tri-Colored Paths
假设三种颜色的边都存在,并且不存在这样的路径 首先观察到,对于一个简单环上的边,颜色一定相同 因此,考虑建立圆方树,问题转化为圆方树上的 D P DP DP问题。限制是对于方点所连接的边,必须涂上相同的颜色…...

基于SSM的实习管理系统
基于SSM的实习管理系统、前后端分离 开发语言:Java数据库:MySQL技术:SpringSpringMVCMyBatisVue工具:IDEA/Ecilpse、Navicat、Maven 系统展示 管理员界面 教师 学生 研究背景 基于SSM的实习管理系统是一个基于Spring、Spring…...

在Vue中通过ElementUI构建前端页面【登录,注册】,在IEDA构建后端实现前后端分离
一.ElementUI组件入门 1.对于ElementUI的理解 是一套基于 Vue.js 的开源UI组件库,提供了丰富的可复用组件,可以帮助开发者快速构建美观、易用的前端界面 2.Element UI 的特点和优势 多样化的组件:Element UI 提供了众多常用的基础组件&#…...
TX2 open ttyTHS2
TX2 open ttyTHS2 #冷风那个吹# 于 2019-04-01 14:10:43 发布 1749 收藏 6 分类专栏: 平时问题积累 TX2 版权 平时问题积累 同时被 2 个专栏收录 22 篇文章0 订阅 订阅专栏 TX2 30 篇文章8 订阅 订阅专栏 TX2上有5个串口,但是ttyTHS1是调试串口,ttyTHS3是蓝牙,ttyTHS…...

conan入门(二十八):解决conan 1.60.0下 arch64-linux-gnu交叉编译openssl/3.1.2报错问题
上一篇博客《conan入门(二十七):因profile [env]字段废弃导致的boost/1.81.0 在aarch64-linux-gnu下交叉编译失败》解决了conan 1.60.0交叉编译boost/1.80.1的问题后,我继续交叉编译openssl/3.1.2时又报错了 conan install openssl/3.1.2 -pr:h aarch64-linux-gnu.…...

Xcode 15 运行<iOS 14, 启动崩溃问题
如题. Xcode 15 启动 < iOS 14(没具体验证过, 我的问题设备是iOS 13.7)真机设备 出现启动崩溃 解决方案: Build Settings -> Other Linker Flags -> Add -> -ld64...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...

MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...

Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...