2167 - 树的公共祖先（LCA）

题目描述

给定一棵树和两个不同的结点，求出他们最近的公共祖先父结点。

已知该树有 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;
}