转自：https://blog.csdn.net/Akatsuki__Itachi/article/details/81279173
关于LCA的Tarjan算法详解可看
https://blog.csdn.net/Septembre_/article/details/81355594
以下是根据算法自行写的模板代码：
vector模拟邻接表：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define eps 1e-8
#define memset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long int LL;
const int MAXL(1e4);
const int INF(0x7f7f7f7f);
const int mod(1e9+7);
int dir[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
int father[MAXL+50];
bool is_root[MAXL+50]; //记录该店是不是根结点
bool vis[MAXL+50]; //标记该点是否被访问过
vector<int>v[MAXL+50]; //存图
int root; //为找到的根结点
int cx,cy; //要查询的两点
int ans;
int Find(int x)
{
if(x!=father[x])
father[x]=Find(father[x]);
return father[x];
}
void Join(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
father[fy]=fx;
}
void LCA(int u)
{
for(int i=0; i<v[u].size(); i++) //对根结点的所有子结点遍历
{
int child=v[u][i];
if(!vis[child])
{
LCA(child); //递归查找每一个结点，直到到叶子结点为止
Join(u,child); //回溯的时候更新father用的
//例如把题目中的[9]更新为5
vis[child]=true; //访问过的点vis数组为true
}
}
if(u==cx&&vis[cy]==true) //若和u有关系的点被访问过,
ans=Find(cy); //则最近公共祖先为那个有关系点的祖先
if(u==cy&&vis[cx]==true) //若没有被访问过，则不操作
ans=Find(cx);
}
void init()
{
memset(is_root,true);
memset(vis,false);
int n;
scanf("%d",&n);
for(int i=0; i<=n; i++)
v[i].clear();
for(int i=1; i<=n; i++)
father[i]=i;
for(int i=1; i<n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
is_root[y]=false; //y点有入度，所以y点不是根结点
}
scanf("%d%d",&cx,&cy); //cx，cy为要查询的两点
for(int i=1; i<=n; i++) //找根结点
{
if(is_root[i]==true)
{
root=i;
break;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init(); //建树（图），找根结点
LCA(root);
cout<<ans<<endl;
}
}
链式前向星写法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define eps 1e-8
#define memset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long int LL;
const int MAXL(1e6);
const int INF(0x7f7f7f7f);
const int mod(1e9+7);
int dir[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
struct node
{
int to;
int next;
}edge[MAXL+50];
int head[MAXL+50];
int father[MAXL+50];
bool vis[MAXL+50];
bool is_root[MAXL+50];
int n;
int cnt;
int cx,cy;
int ans;
int root;
int Find(int x)
{
if(x!=father[x])
father[x]=Find(father[x]);
return father[x];
}
void Join(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
father[fy]=fx;
}
void add_edge(int x,int y)
{
edge[cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt++;
}
void init()
{
cnt=0;
memset(head,-1);
memset(vis,false);
memset(is_root,true);
scanf("%d",&n);
for(int i=0;i<=n;i++)
father[i]=i;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
is_root[y]=false;
}
for(int i=1;i<=n;i++)
if(is_root[i]==true)
root=i;
}
void LCA(int u)
{
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
LCA(v);
Join(u,v);
vis[v]=true;
}
if(cx==u&&vis[cy]==true)
ans=Find(cy);
if(cy==u&&vis[cx]==true)
ans=Find(cx);
}
void solve()
{
scanf("%d%d",&cx,&cy);
LCA(root);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
solve();
cout<<ans<<endl;
}
}