当前位置: 首页 > news >正文

prufer板子

prufer:
一种将带标号的树用一个唯一的长度为\(n-2\)整数序列表示的方法。

Prüfer 是这样建立的:
每次选择一个编号最小的叶结点并删掉它,然后在序列中记录下它连接到的那个结点。重复 𝑛 −2

        rep(i,1,n-1){cin>>f[i];deg[i]++;deg[f[i]]++;}int pos=1;for(int i=1;i<=n-2;i++){while(deg[pos]!=1)pos++;p[i]=f[pos];while(i<=n-2 && --deg[p[i]]==1 && p[i]<pos){p[i+1]=f[p[i]];i++;}pos++;}

Prüfer 序列的性质
在构造完 Prüfer 序列后原树中会剩下两个结点,其中一个一定是编号最大的点 𝑛
每个结点在序列中出现的次数是其度数减 1
(没有出现的就是叶结点)

prufer重构树:

        rep(i,1,n)deg[i]++;for(int i=1;i<=n-2;i++){cin>>p[i];deg[p[i]]++;}p[n-1]=n;int pos=1;rep(i,1,n-1){while(deg[pos]!=1)pos++;f[pos] = p[i];while(i<=n-1 && --deg[p[i]]==1 && p[i]<pos){f[p[i]]=p[i+1];i++;}pos++;}
http://www.hskmm.com/?act=detail&tid=35687

相关文章:

  • 军用混合现实头盔EagleEye的技术解析
  • 2025电子数据取证分析师WriteUp
  • 03.Python百行代码实现点赞系统
  • Promise多个then、catch、finally的执行结果分析与总结
  • Search-R1论文浅析与代码实现
  • Ai元人文构想:技术介入人文领域的辩证思考与路径探索
  • 2025年10月医用面膜产品推荐:权威对比评测榜助术后修护精准决策
  • 2025年10月电动叉车销售公司推荐:五强对比评测榜
  • 类方法和实例方法区别 flutter
  • 今天给电脑安装了新华财经
  • 2025电子数据取证分析师Wp
  • 2025年10月仓储管理系统推荐榜:鸿链云仓领衔对比评测排行
  • NITEX:构建时尚新供应链的数字平台与技术架构
  • 电子人速囤!正点原子万用表,电烙铁,电桥镊子等商品!
  • 2025年10月超声波清洗机厂家榜单:十家主流厂商横向对比
  • 2025年10月超声波清洗机厂家评价榜:实力对比一览
  • 2025年10月炒股开户券商评测榜:广发证券领衔全维度对比
  • 2025年10月超声波清洗机厂家评测榜:十强对比与权威数据解读
  • 2025年10月超声波清洗机厂家推荐榜:十强对比评测
  • 2025 年桥梁护栏厂家最新推荐排行榜:聚焦安全防护与耐用性能的实力企业甄选指南
  • 在Java中,如何实现封装
  • 2025年10月超声波清洗机厂家排行:十家主流企业深度评测
  • 2025年10月不锈钢水箱厂家推荐榜:十强对比评测
  • 2025年10月不锈钢水箱厂家排行:十家对比评价
  • 2025年10月长白山旅游度假酒店推荐:口碑榜与实景对比排行
  • 2025 年最新推荐北京 / 陕西百度官网认证代理商榜单:全方位评估服务实力助企业选靠谱机构
  • 2025年10月长白山度假酒店推荐:民俗与国际范双榜对比
  • skynet.dispatch 使用详解
  • 深入解析:开源项目net-radio-archive常见问题解决方案
  • 元推理:自指生产力,自洽生产关系