博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj1330 Nearest Common Ancestors
阅读量:5025 次
发布时间:2019-06-12

本文共 1159 字,大约阅读时间需要 3 分钟。

题目链接

题意

给定一棵树和树上的两个结点,输出这两个结点的最近公共祖先。

思路

题目给定了两个结点a,b,我的思路是分别求出a,b的所有祖先,保存在va,vb中,然后遍历va和vb,由于va和vb中的结点是按离树根越来越近排列的,所以va和vb中第一个重合的元素即为a,b的最近公共祖先。在树的表示方面,使用数组来存储树。

代码

1 #include 
2 #include
3 #include
4 #include
5 using namespace std; 6 7 const int N = 10000 + 10; 8 int p[N]; //p[i]表示结点i的双亲结点 9 vector
va; //结点a的所有祖先结点10 vector
vb; //结点b的所有祖先结点11 12 void find_ancestor(int c, vector
& v) //找到c的祖先,存储在v中13 {14 if(p[c] == 0) //树的根结点15 {16 v.push_back(c);17 return;18 }19 20 v.push_back(c);21 find_ancestor(p[c], v);22 }23 24 void get_nca(int a, int b)25 {26 va.clear();27 vb.clear();28 find_ancestor(a, va);29 find_ancestor(b, vb);30 31 int la = va.size();32 int lb = vb.size();33 34 for(int i=0; i
>t;52 while(t--)53 {54 memset(p, 0, sizeof(p));55 int n;56 cin>>n;57 for(int i=0; i
>a>>b;61 p[b] = a;62 }63 int a, b;64 cin>>a>>b;65 get_nca(a, b);66 }67 return 0;68 }

转载于:https://www.cnblogs.com/sench/p/7815790.html

你可能感兴趣的文章
Eclipse导入maven项目时,Pom.xml文件报错处理方法
查看>>
01、JAVA开发准备
查看>>
asp.net mvc 错误处理 - 自定义报错处理,生成错误日志
查看>>
Linux centos ssh
查看>>
R语言之避免for循环示例
查看>>
[转]jQuery 选择器和dom操作
查看>>
Jenkins+Maven+SVN快速搭建持续集成环境(转)
查看>>
bootstrap 媒体查询
查看>>
杜教筛
查看>>
《Ext JS模板与组件基本知识框架图----模板》
查看>>
txmpp
查看>>
微信开发时调用jssdk,在安卓设备中成功调用;在ios设备中返回错误消息:config fail,无其他具体错误消息,且接口权限显示获取ok,无法调用...
查看>>
【Github教程】史上最全github使用方法:github入门到精通
查看>>
抽象工厂模式(Abstract Factory)
查看>>
luogu1373 小a和uim之大逃离 (dp)
查看>>
Redis的Pub/Sub客户端实现
查看>>
SQL日常问题和技巧——持续更新
查看>>
springMVC入门(一)------springMVC基本概念与安装
查看>>
Sam做题记录
查看>>
[bzoj] 2453 维护数列 || 单点修改分块
查看>>