【图论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 的 区别

有向无环图:不能从某点开始经过数点回到该点

有根树 都是 DAGDAG 不一定是 有根树(如下图:虽然没有构成环,但是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 2n50000 。组织成员的编号为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]=nDegree[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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144730.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Neo4j-双向关系

概述 这是GraphAware中关于双向关系的解释。 网址链接Modelling Data in Neo4j: Bidirectional Relationships | GraphAware 定向关系 Neo4j中的关系必须有一个语义化的类型和方向。 没有方向关系是模棱两可的&#xff0c;上面A队打败B队&#xff0c;如果没有方向&#xff0c…

AOP 编程

目录 ​编辑一、AOP 编程 1、AOP 概念 2、AOP 编程的开发步骤 3、切面的名词解释 二、AOP 的底层实现原理 1、核心问题 2、动态代理类的创建 &#xff08;1&#xff09;JDK 的动态代理创建 &#xff08;2&#xff09;CGlib 的动态代理 &#xff08;3&#xff09;总结…

支持笔记本电脑直插直充,TOWE 65W智能快充PDU超级插座

电源插排在我们的生活中是必不可少的电器配件。今天&#xff0c;我们日常生活中所使用的电子设备越来越多&#xff0c;无论是手机、平板、笔记本电脑还是各种家用电器&#xff0c;都需要电源来驱动。虽然相对于其他电器来说&#xff0c;插排结构比较简单&#xff0c;但现代家庭…

设计模式5、原型模式 Prototype

解释说明&#xff1a;使用原型实例指定待创建对象的类型&#xff0c;并且通过复制这个原型阿里创建型的对象 UML 结构图&#xff1a; 抽象原型&#xff08;Prototype&#xff09;&#xff1a;规定了具体原型对象必须实现的clone()方法 具体原型&#xff08;ConcretePrototype&…

【我的创作纪念日】使用pix2pixgan实现barts2020数据集的处理(完整版本)

使用pix2pixgan &#xff08;pytorch)实现T1 -> T2的基本代码 使用 https://github.com/eriklindernoren/PyTorch-GAN/ 这里面的pix2pixgan代码进行实现。 进去之后我们需要重新处理数据集&#xff0c;并且源代码里面先训练的生成器&#xff0c;后训练鉴别器。 一般情况下…

计算机图像处理-均值滤波

均值滤波 线性滤波器的原始数据与滤波结果是一种算术运算&#xff0c;即用加减乘除等运算实现&#xff0c;如均值滤波器&#xff08;模板内像素灰度值的平均值&#xff09;、高斯滤波器&#xff08;高斯加权平均值&#xff09;等。由于线性滤波器是算术运算&#xff0c;有固定…

Android Jetpack Compose之确定重组范围并优化重组

1.概述 Compose的重组是智能的&#xff0c;Composable函数在进行重组时会尽可能的跳过不必要的重组&#xff0c;只对需要变化的UI进行重组。那Compose是如何认定UI需要变化呢&#xff1f;或者换句话说Compose是如何确定重组的范围呢。如果重组随意的发生&#xff0c;那么对UI的…

LabVIEW开发实时自动化多物镜云计算全玻片成像装置

LabVIEW开发实时自动化多物镜云计算全玻片成像装置 数字病理学领域正在迅速发展&#xff0c;这主要是由于计算机处理能力、数据传输速度、软件创新和云存储解决方案方面的技术进步。因此&#xff0c;病理科室不仅将数字成像用于图像存档等简单任务&#xff0c;还用于远程病理学…

一些 dp 题

CYEZ 弹珠 key&#xff1a;思维题&#xff0c;完全背包。 先每个组分一个小球。等价于 n − k n-k n−k 拆分为任意个 [ 1 , k ] [1,k] [1,k] 的数的方案数。 本质是根据面积的转换&#xff0c;直观解释&#xff1a; 完全背包即可。代码。 No Bug No Game key&#xff1…

无人直播间

失败&#xff01;&#xff01; 采用 ffmpeg 技术进行推流 推流代码&#xff1a; 【需要将rtmp替换为你的推流地址】 ffmpeg -re -stream_loop -1 -i "rain.mp4" -c copy -f flv ""推流地址获取 以哔哩哔哩为例 点击下方链接 开播设置 - 个人中心 - …

Java编程技巧:文件上传、下载、预览

目录 1、上传文件1.1、代码1.2、postman测试截图 2、下载resources目录中的模板文件2.1、项目结构2.2、代码2.3、使用场景 3、预览文件3.1、项目结构3.2、代码3.3、使用场景 1、上传文件 1.1、代码 PostMapping("/uploadFile") public String uploadFile(Multipart…

麒麟信安服务器操作系统V3.5.2重磅发布!

9月25日&#xff0c;麒麟信安基于openEuler 22.03 LTS SP1版本的商业发行版——麒麟信安服务器操作系统V3.5.2正式发布。 麒麟信安服务器操作系统V3定位于电力、金融、政务、能源、国防、工业等领域信息系统建设&#xff0c;以安全、稳定、高效为突破点&#xff0c;满足重要行…

试图一文彻底讲清 “精准测试”

在软件测试中&#xff0c;我们常常碰到两个基本问题&#xff08;困难&#xff09;&#xff1a; 很难保障无漏测&#xff1a;我们做了大量测试&#xff0c;但不清楚测得怎样&#xff0c;对软件上线后会不会出问题&#xff0c;没有信心&#xff1b; 选择待执行的测试用例&#…

阿里云七代云服务器实例、倚天云服务器及通用算力型和经济型实例规格介绍

在目前阿里云的云服务器产品中&#xff0c;既有五代六代实例规格&#xff0c;也有七代和八代倚天云服务器&#xff0c;同时还有通用算力型及经济型这些刚推出不久的新品云服务器实例&#xff0c;其中第五代实例规格目前不在是主推的实例规格了&#xff0c;现在主售的实例规格是…

MySQL架构 InnoDB存储引擎

1. 什么是Mysql&#xff1f; 我们在开发的时候&#xff0c;我们都需要对业务数据进行存储&#xff0c;这个时候&#xff0c;你们就会用到MySQL、Oracal等数据库。 MySQL它是一个关系型数据库&#xff0c;这种关系型数据库就有Oracal、 MySQL&#xff0c;以及最近很火的PgSQL等。…

Springcloud实战之自研分布式id生成器

一&#xff0c;背景 日常开发中&#xff0c;我们需要对系统中的各种数据使用 ID 唯一表示&#xff0c;比如用户 ID 对应且仅对应一个人&#xff0c;商品 ID 对应且仅对应一件商品&#xff0c;订单 ID 对应且仅对应 一个订单。我们现实生活中也有各种 ID &#xff0c;比如身…

分享78个Python源代码总有一个是你想要的

分享78个Python源代码总有一个是你想要的 源码下载链接&#xff1a;https://pan.baidu.com/s/1ZhXDsVuYsZpOUQIUjHU2ww?pwd8888 提取码&#xff1a;8888 下面是文件的名字。 12个python项目源码 Apache Superset数据探查与可视化平台v2.0.1 API Star工具箱v0.7.2 Archery…

Springcloud:二、Eureka介绍+上手(搭建EurekaServer注册中心+服务注册+服务拉取)

Eureka介绍 Eureka上手 搭建EurekaServer注册中心 在cloud-demo这个maven项目下创建eureka-server模块 引入依赖 在eureka-server模块的pom文件中新增如下代码 <dependencies><dependency><groupId>org.springframework.cloud</groupId><artif…

安卓:解决AndroidStudio导出Unity的Apk(APP)出现2个显示图标

用AndroidStudio打开该项目 实现只保留1个app图标 AndroidManifest.xml的改法如下&#xff1a; <?xml version"1.0" encoding"utf-8"?> <manifest xmlns:android"http://schemas.android.com/apk/res/android" package"com.fru…

uniapp iOS离线打包——原生工程配置

uniapp iOS离线打包&#xff0c;如何配置项目工程&#xff1f; 文章目录 uniapp iOS离线打包&#xff0c;如何配置项目工程&#xff1f;工程配置效果图DebugRelease 配置工程配置 Appkey应用图标模块及三方SDK配置未配置模块错误配置模块TIP: App iOS 离线打包 前提&#xff1a…