求LCA最近公共祖先的离线Tarjan算法

求LCA最近公共祖先的离线Tarjan算法_C++

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

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

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

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

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

　　　　http://www.cnblogs.com/hadilo/p/5837517.html

　　直接上伪代码：

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

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

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<stack>
 8 #define N 100001
 9 using namespace std;
10 
11 int down[N],next[N],f[N],ans[N],n;
12 stack<int> s[N],num[N];
13 int find(int x)
14 {
15   return f[x]==x?x:f[x]=find(f[x]);
16 }
17 void dfs(int x)
18 {
19     f[x]=x;
20     int i;
21     for (i=down[x];i!=0;i=next[i])
22         {
23             dfs(i);
24             f[find(f[i])]=find(f[x]);
25         }
26     while (!s[x].empty())
27       {
28         if (f[s[x].top()]!=s[x].top()) ans[num[x].top()]=find(f[s[x].top()]);
29         s[x].pop();
30         num[x].pop();
31       }
32 }
33 int main()
34 {
35     freopen("lca.in","r",stdin);
36     freopen("lca.out","w",stdout);
37     int i,x,y,t,root;
38     scanf("%d",&n);
39     for (i=1;i<=n;i++)
40         {
41             scanf("%d",&x);
42             next[i]=down[x];
43             down[x]=i;
44             if (x==0) root=i;
45         }
46     scanf("%d",&t);
47     for (i=1;i<=t;i++)
48         {
49             scanf("%d%d",&x,&y);
50             if (x==y) ans[i]=x;
51             s[x].push(y);
52             s[y].push(x);
53             num[x].push(i);
54             num[y].push(i);
55         }
56     dfs(root);
57     for (i=1;i<=t;i++) printf("%d
",ans[i]);
58     return 0;
59 }

QQ：740929894