本文共 1139 字，大约阅读时间需要 3 分钟。

 

　　这个Tarjan算法是求LCA的算法，不是那个强连通图的

　　它是 离线 算法，时间复杂度是 O(m+n)，m 是询问数，n 是节点数

　　它的优点是比在线算法好写很多

　　不过有些题目是强制在线的，此类离线算法就无法使用了

　　另附上在线ST算法的链接：

　　　　

---

 

　　直接上伪代码：

　　源代码中将询问用栈分节点一个个压入，而且克隆了单次询问，如询问 1 5 节点，则将 5 压入 1 的栈中，并且将 5 压入 1 的栈中

　　因为当询问时会有一次另一个还未加入并查集的情况

 

#include<algorithm>

#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<stack> #define N 100001 using namespace std;

int down[N],next[N],f[N],ans[N],n;

stack<int> s[N],num[N]; int find(int x) {   return f[x]==x?x:f[x]=find(f[x]); } void dfs(int x) {     f[x]=x;     int i;     for (i=down[x];i!=0;i=next[i])         {             dfs(i);             f[find(f[i])]=find(f[x]);         }     while (!s[x].empty())       {         if (f[s[x].top()]!=s[x].top()) ans[num[x].top()]=find(f[s[x].top()]);         s[x].pop();         num[x].pop();       } } int main() {     freopen("lca.in","r",stdin);     freopen("lca.out","w",stdout);     int i,x,y,t,root;     scanf("%d",&n);     for (i=1;i<=n;i++)         {             scanf("%d",&x);             next[i]=down[x];             down[x]=i;             if (x==0) root=i;         }     scanf("%d",&t);     for (i=1;i<=t;i++)         {             scanf("%d%d",&x,&y);             if (x==y) ans[i]=x;             s[x].push(y);             s[y].push(x);             num[x].push(i);             num[y].push(i);         }     dfs(root);     for (i=1;i<=t;i++) printf("%d\n",ans[i]);     return 0; }

 

 

转载地址：http://bwuii.baihongyu.com/