请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

如何构建虚树

[复制链接]
查看: 39|回复: 0

7856

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
31850
发表于 2019-11-9 09:23 | 显示全部楼层 |阅读模式
怎样构建虚树?

当我们获得k个关键点后
首先把关键点按dfn(即原树的dfs序)从小到大排序
然后开一个栈
栈的意义(性质):从栈底到栈顶的元素组成(表示)虚树中从上到下的一条链
虚树构建进程:
依次罗列关键点x
<ul>
当栈为空或栈中只要一个元素(即top=dfn[lca]){        ADD(stk[top-1],stk[top]); // 单向         --top;    }    if(lca!=stk[top]){        ADD(lca,stk[top]);        stk[top]=lca;    }    stk[++top]=x;}int main(){    ...    sort(x+1,x+k+1,cmp); //按dfn从小到大     top=0;ans=0;    stk[++top]=1;    for(int i=1;i1)ADD(stk[top-1],stk[top]),--top;    ...}[/code]
免责声明:假如加害了您的权益,请联系站长,我们会实时删除侵权内容,感谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 妈妈网-中国妈妈第一,是怀孕、育儿、健康等知识交流传播首选平台 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表