【图论C++】树的重心——教父POJ 3107(链式前向星的使用)

这篇具有很好参考价值的文章主要介绍了【图论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 树上问题

  • 的一种特例 就是 “没有环”连通图

判断一个 是否是一个 ,需要满足的条件:

  • 1)树根:一棵树可以基于无向图有向图,区别在于树根。

    基于无向图的树(无根树),是没有固定树根的(也就是说树根的个数可能不止为1,或说每个结点都能做为树根)

    基于有向图的树(有根树),有且仅有一个树根

  • 2)父节点与子节点的关系:每个节点有且仅有一个父节点。从根节点遍历,必须由父节点遍历到子节点

  • 3)连通性:从 根 出发可以遍历树上所有(除根节点外)节点,且到这些节点的路径只有一条

有根树 与 有向无环图 DAG 的 区别

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

有根树 都是 DAGDAG 不一定是 有根树(如下图:虽然没有构成环,但是4号节点同时拥有两个父节点,不符合有根树的定义)

【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先

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节点 为 树的重心。

【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先

可以一眼看出: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 重心的性质

  • 以树的重心为根时,所有子树的大小都不超过整棵树大小的一半。(树上分治会用到
【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先
  • 树的重心如果不唯一,则至多有两个,且这两个重心相邻
【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先
  • 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么到它们的距离和一样
【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先
  • 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上
【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先
  • 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。(往树上增加或减少一个叶子,如果原节点数是奇数,那么重心可能增加一个,原重心仍是重心;如果原节点数是偶数,重心可能减少一个,另一个重心仍是重心

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就可以解决问题。

【图论C++】树的重心——教父POJ 3107(链式前向星的使用),C++算法,数据结构,c++,网络,算法,深度优先

如上图,假如删除 结点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]

存储:链式前向星

链式前向星领接矩阵(二维数组)在空间上优化了很多

点击直通 链式前向星(图(树)的存储)文章来源地址https://www.toymoban.com/news/detail-729961.html

  • 代码
#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(链式前向星的使用)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 蓝桥集训之BFS、DFS和链式前向星

    https://www.bilibili.com/video/BV1RD4y1F7Fq 图一般定义为 二元集 ; 由 顶点集 与 边集 构成。 或者更抽象的说,由一个集合(顶点),和集合上的关系(边)构成 邻接矩阵 邻接表 度,出度,入度 在有向图中,箭头是具有方向的,从一个顶点指向另一个顶点,这样一来,每个顶点 被指

    2023年04月09日
    浏览(37)
  • 图的存储--邻接矩阵/边集数组/邻接表/链式邻接表/链式前向星

    使用二维数组w[u][v]存储点u到点v的边的权值。 一般应用在点数不多的稠密图 时间复杂度:O(n 2 ) 空间复杂度:O(n 2 ) 边集数组e[i]存储第i条边的「起点、终点、边权」。在kruskal算法中,将边按边权排序,直接存边。 时间复杂度:O(nm) 空间复杂度:O(m) 出边数组e[u][i]存储u的所

    2024年02月02日
    浏览(37)
  • 算法复习6.1链式前向星(代码块式理解)

    一号初始节点head[1]=3(cnt=3)指向四号节点 edge[3(cnt=3)],其中edge[3].to=4 即四号节点 ,同时令edge[3].next=(new)cnt 指向下一个 ... (循环) 有点像指针,如果功能不复杂的话,可以直接简写为vector快捷操作  

    2024年02月21日
    浏览(56)
  • 【算法每日一练]-图论(保姆级教程篇16 树的重心 树的直径)#树的直径 #会议 #医院设置

    目录 树的直径 题目:树的直径 (两种解法) 做法一:   做法二: 树的重心: 题目: 会议  思路: 题目:医院设置  思路:                   定义:树中距离最远的两个点之间的距离被称为树的直径。 一共有两种做法,先记结论,再给证明!  做法一: (1)任

    2024年04月23日
    浏览(46)
  • [C++][算法基础]树的重心(树图DFS)

    给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心

    2024年04月12日
    浏览(35)
  • acwing 846. 树的重心

    给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

    2023年04月15日
    浏览(27)
  • AcWing 846. 树的重心(dfs)

    这是一道我一开始没怎么看懂的题目,然后后面看了y神的讲解就豁然开朗了 不过我们首先要有先置知识来理解这道题目 邻接表 :是一种表示图的数据结构,它通过链表的方式记录每个顶点及其相邻的顶点。在这个具体的问题中,使用数组 h 来表示邻接表。 h 数组: h 数组的

    2024年02月02日
    浏览(32)
  • 【算法每日一练]-图论(保姆级教程篇12 tarjan篇)#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

    目录: 今天知识点 加边使得无向图图变成双连通图 找出度为0的强连通分量 加边使得有向图变成强连通图 将有向图转成DAG图进行dp          POJ3352:道路建设         思路: POJ2553:图的底部 思路: POJ1236校园网络 思路: 缩点:  思路:          由于道路要维修

    2024年02月05日
    浏览(42)
  • 【图论C++】树的直径(DFS 与 DP动态规划)

    UpData Log👆 2023.9.27 更新进行中 Statement0🥇 一起进步 Statement1💯 有些描述是个人理解,可能不够标准,但能达其意 21-1-1 定义 树上 最远的两个节点之间 的距离被称为 树的直径 ,连接这两个点的路径 被称为 树的最长链 。 21-1-2 性质 1 、这两个最远点一定是叶子节点 1、这 两

    2024年02月07日
    浏览(40)
  • 数据结构与算法—二叉树数组表示(ArrayBinTree)、二叉树的链式表示(LinkedBinTree)的基于C++模板代码实现

    1、二叉树的顺序表示:ArrayBinTree.h 二叉树的顺序表示法操作方便,但缺点是容易造成存储空间浪费。 这是一个用数组实现的二叉树类模板。它可以创建一个空树,也可以在指定的位置插入结点并设置结点的值,可以删除子树,并支持逐层遍历。使用该类时,需要提供一个元

    2024年02月06日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包