1.前言
首先我们介绍的算法是LCA问题中的离线算法-Tarjan算法，该算法采用DFS+并查集，再看此算法之前首先你得知道并查集（尽管我相信你如果知道这个的话肯定是知道并查集的），Tarjan算法的优点在于相对稳定，时间复杂度也比较居中，也很容易理解（个人认为）。
2.思想
下面详细介绍一下Tarjan算法的思想：
1.任选一个点为根节点，从根节点开始。
2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。
3.若是v还有子节点，返回2，否则下一步。
4.合并v到u上。
5.寻找与当前点u有询问关系的点v。
6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。
从上面步骤可以看出，Tarjan算法要用到并查集。这里，我们使用链式前向星来存储边和询问情况。
3.算法实现
不妨以洛谷P3379：LCA模板题为例题
#include<cstdio>
#include<cstring> const int maxn = 5e5 + ,maxm = 5e5 + ;
int fa[maxn],fir[maxn],frt[maxn],ans[maxm],n,m,s,tot,id;
bool flag[maxn];
//存边
struct Edge{
int v,next;
}e[maxn << ];
//存询问
struct Ques{
int v,next,qid;
}q[maxm << ];
//加边
void addEdge(int u,int v){
e[tot] = (Edge){v,fir[u]};
fir[u] = tot++;
e[tot] = (Edge){u,fir[v]};
fir[v] = tot++;
}
//加询问
void addQues(int u,int v,int qid){
q[id] = (Ques){v,frt[u],qid};
frt[u] = id++;
q[id] = (Ques){u,frt[v],qid};
frt[v] = id++;
}
//读入优化
inline int read(){
int sum = ;
char ch = getchar();
while(ch < '' || ch > '') ch = getchar();
while(ch >= '' && ch <= ''){sum = sum * + ch - ''; ch = getchar();}
return sum;
}
//输出优化
void write(int x){
if(x / ) write(x / );
putchar(x % + '');
}
//寻找父亲
int find(int x){
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
//合并
void unionn(int x,int y){
int fx = find(x),fy = find(y);
fa[fx] = fy;
}
//离线操作(u表示当前点，fa表示该点的前驱点)
void dfs(int u,int fa){
flag[u] = true;//标记已访问
//遍历所有与u相连的点
for(int i = fir[u];i != -;i = e[i].next){
int v = e[i].v;
//如果v不是u的前驱
if(v != fa){
dfs(v,u);//遍历下一层
//寻找是否有询问关系
for(int j = frt[v];j != -;j = q[j].next){
int k = q[j].v;
if(flag[k])
ans[q[j].qid] = find(k);
}
unionn(v,u);//连接
}
}
}
//主函数
int main(){
n = read(),m = read(),s = read();
memset(fir,-,sizeof(fir));
memset(frt,-,sizeof(frt));
for(int i = ;i < n;i++){
fa[i] = i;
int x = read(),y = read();
addEdge(x,y);
}
fa[n] = n;
for(int i = ;i <= m;i++){
int x = read(),y = read();
addQues(x,y,i);
}
dfs(s,-);
//因为这里已经给出根了，直接从根开始
for(int i = ;i <= m;i++,putchar('\n')) write(ans[i]);
return ;
}