首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

算法anscetor解决思路

2012-03-15 
算法anscetor★数据输入第 1 行有一个正整数 n(1n1000),表示给定的树有 n 个节点,编号为 1,2,…,n,编号为1

算法anscetor
★数据输入
第 1 行有一个正整数 n(1<n<1000),表示给定的树有 n 个节点,编号为 1,2,…,n,
编号为1 的顶点是树根。接下来的 n行中,第 i+1行描述与 i节点相关联的子节点的信息。
每行的第 1 个正整数 k 表示该节点的儿子节点数。其后第 k 个数中,每一个数表示一个儿
子节点的编号,当 k=0 时表示相应的节点是叶节点。
文件的第 n+2 行是一个正整数 m(1<m<100),表示要计算最近公共祖先的 m 个节
点对。接下来的 m 行,每行两个正整数,计算最近公共祖先的节点编号。
★数据输出
将计算出的m个节点对的最近公共祖先节点编号输出。每行3个整数,前两个是节点对
编号,第三个是他们的最近公共祖先节点编号。

[解决办法]
对节点计算其从根节点算起的路径,然后比对节点对的路劲,找到从根节点算起的最后一个相同的节点,即为最近的公共祖先

热点排行