最近公共祖先(LCA)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

/**************************************************************** 
 * Description: C++  Lowest Common Ancestor
 * Author: Alex Li
 * Date: 2022-08-10 12:28:52
 * LastEditTime: 2024-05-09 09:19:53
****************************************************************/

#include <iostream>
#include <vector>
using namespace std;
const int maxn=1000;
int n,r,a,b;//n为边个数，r为根结点,a和b为具体结点，
int fa[maxn]; //fa数组是父结点编号。
bool vis[maxn];  //记录祖先结点
vector<int> g[maxn];  //用一个动态数组表示图的邻接表关系

void dfs(int u){
    int j=g[u].size();
    for (int i = 0; i < j; i++){
        int v=g[u][i];
        if(v==fa[u])continue;   //如果是父结点，就忽略后面语句，继续循环
         fa[v]=u;       //记录v结点的父结点是u
         dfs(v);        //递归，深度搜索
    }
    
}
int LCA(int x,int y){
       memset(vis,0,sizeof(vis));//给vis数组清零
       //把所有x结点的父结点都用vis数组标注出来 
       while(x){
        vis[x]=true;
        x=fa[x];
       }
       //找y数组的祖先，如何遇见已经被访问vis[]=true，就是x,y的最近共同祖先
       while(!vis[y])y=fa[y];
       return y;       
}
int main(){
    
    cin>>n>>r;
    //g[]记录树
    for (int i = 1;i <=n; i++){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
   //深搜，用fa[]数组记录每个结点的父结点
    dfs(r);  //r为根结点
    //输入两个结点 
    cin>>a>>b;
    //找到两个结点的共同祖先
    cout<<LCA(a,b);
return 0;
    
}