题目描述
给定一棵树和两个不同的结点，求出他们最近的公共祖先父结点。
已知该树有 n 个结点，标号 1..n 。
输入
第 1 行输入一个整数 nn，代表结点数量（n≤100）
第 2 行输入两个整数 x,yx,y，表示需要计算的结点；
以下 n−1 行，每行两个整数 a 和 b，表示 a 的父结点是 b。
输出
输出 x 与 y 的最近公共祖先 root。
样例
输入
复制
9 9 7 2 1 3 2 4 2 5 3 8 5 9 5 6 4 7 4
输出
复制
2
首先，这题只需要分别从x和y往上进行搜索，路线产生的第一个交点就是答案
说人话就是vis记录路径然后判断什么时候重合
代码很短：
#include<iostream> #include<vector> using namespace std; int root,fa[105]; int n,a,b,x,y; bool vis[105]; //可以用vector但是没必要 // vector <int> q[105]; int main(){ scanf("%d%d%d",&n,&x,&y); //并查集fa数组初始化 for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=n-1;i++){ scanf("%d%d",&a,&b); fa[a]=b; } //防止数据阴人 if(x==y){ printf("%d",x); return 0; } //标记x走过 vis[x]=1; //找每一个x的父亲 while(fa[x]!=x){ x=fa[x]; vis[x]=1; } //然后从y开始往上找 while (fa[y]!=y) { y=fa[y]; if(vis[y]==1){ cout<<y; break; } } return 0; }