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

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

阅读量：5321 次

发布时间：2019-06-14

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

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

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

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

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

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

　　直接上伪代码：

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

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

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define N 100001 9 using namespace std;10 11 int down[N],next[N],f[N],ans[N],n;12 stack
            
              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\n",ans[i]);58 return 0;59 }