LCA Nearest Common Ancestors (很典型的例题)
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
Output
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=1E4+;
bool pre[N];
vector<int >ve[N];
typedef long long ll;
ll bits[];
int depth[N],fa[N][];
void inint(){
bits[]=;
for(int i=;i<=;i++) bits[i]=bits[i-]<<;
}
void dfs(int x,int y){
depth[x]=depth[y]+;
fa[x][]=y;
for(int i=;i<=;i++){
fa[x][i]=fa[fa[x][i-]][i-];
}
for(int i=;i<ve[x].size();i++){
int x1=ve[x][i];
if(x1!=y){
dfs(x1,x);
}
}
}
int lca(int x,int y){
if(depth[x]<depth[y]) swap(x,y);
int dif=depth[x]-depth[y];
for(int i=;i>=;i--){
if(dif>=bits[i]){
x=fa[x][i];
dif-=bits[i];
}
}
if(x==y) return x;
for(int i=;i>=;i--){
if(depth[x]>=bits[i]&&fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][];
} int main(){
int t;
inint();
scanf("%d",&t);
while(t--){
memset(pre,,sizeof(pre));
memset(fa,,sizeof(fa));
memset(depth,,sizeof(depth));
int n;
scanf("%d",&n);
int x,y;
for(int i=;i<=n-;i++){
scanf("%d%d",&x,&y);
ve[x].push_back(y);
ve[y].push_back(x);
pre[y]=;
}
int ancestor; for(int i=;i<=n;i++){
if(pre[i]==){
ancestor=i;
break;
}
}
dfs(ancestor,);
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y)); for(int i=;i<=n;i++){
ve[i].clear();
}
}
return ;
}
还可以用 暴力 朴素算法来算
#include<stdio.h>///LCA最近公共祖先查询,朴素算法
#include<string.h>
int fa[]; int deep(int x)///计算x节点深度
{
int cnt=;
while(x)
{
cnt++;
x=fa[x];
}
return cnt;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
memset(fa,,sizeof(fa));///该数组记录每个节点的父亲,根节点父亲为0
int s,f;
scanf("%d",&n);
for(int i=;i<n-;i++){
scanf("%d%d",&f,&s);
fa[s]=f;
} int a,b;
scanf("%d%d",&a,&b);
int x1=deep(a),y1=deep(b);
//只是用深度做了一个判断 取了一个差。
if(x1<y1)///查询的深度若两个节点深度不同,将较深的节点先上移
{
int tt=y1-x1;
while(tt--)
b=fa[b];
}
else if(x1>y1){
int tt=x1-y1;
while(tt--)
a=fa[a];
} while(a!=b)///两个节点深度相同时同时向上寻找父亲,直到父亲相同
a=fa[a],b=fa[b];
printf("%d\n",a);
}
}
最新文章
- php分页原理
- <;welcome-file-list>;标签的控制作用以及在springmvc中此标签的的配置方式
- aspcms标签
- Python 开发轻量级爬虫02
- 《BI项目笔记》创建多维数据集Cube(2)
- paip.截取字符串byLastDot方法总结uapi python java php c# 总结
- 【转载】CMake 简介和 CMake 模板
- shell 下的$符合
- iOS中属性Property的常用关键字的使用说明
- JAVA 构造代码块
- OS X中如何获取当前运行程序的路径
- [译] 开发者角度,王道之论:Android 与 Windows Phone
- UNIX基础--Shells
- 邮件实现详解(四)------JavaMail 发送(带图片和附件)和接收邮件
- Nytro MegaRaid
- JavaScript内置的预定义函数
- Web Service进阶(三)HTTP-GET, HTTP-POST and SOAP的比较
- ";《算法导论》之‘图’";:最小生成树(无向图)
- 支持向量机SVM原理_python sklearn建模乳腺癌细胞分类器(推荐AAA)
- SRS流媒体服务器安装配置
热门文章
- 动态规划-Last Stone Weight II
- 李宏毅老师机器学习课程笔记_ML Lecture 0-1: Introduction of Machine Learning
- 通过源码理解Spring中@Scheduled的实现原理并且实现调度任务动态装载
- 如何实现浏览器的Console功能
- python入门灵魂5问--python学习路线,python教程,python学哪些,python怎么学,python学到什么程度
- 多源第k短路 (ford + 重新定义编号) / 出发点、终点确定的第k短路 (Spfa+ 启发搜索)
- JS去除字符串内的空白字符方法
- Spring MVC 笔记--配置基于JavaConfig
- .NET Core项目部署到Linux(Centos7)(九)防火墙配置,允许外网或局域网访问.NET Core站点
- docker 容器容器之间网络通信 docker-compose.yaml 配置固定ip