LCA線上算法詳解

LCA（最近公共祖先）的求法有多種，這裡先介紹第一種：線上算法。

線上算法就是利用了DFS和RMQ兩種算法，它先是預處理好所有情況，然後根據輸入輸出答案，在輸入比較多的時候用比較好。

上面兩張圖介紹了線上算法的做法，要了解并不難，下面附上實作代碼：

1 /*******************************
 2 dfs實作代碼
 3 *******************************/
 4 
 5 void dfs(int u, int dep)
 6 {
 7     vis[u]=1;
 8     ver[++tot]=u;   //周遊序列
 9     first[u]=tot;   //結點第一次出現位置
10     deep[tot]=dep;     //深度
11     for(int i=head[u];i!=-1;i=e[i].next)
12     {
13         if(!vis[e[i].v])
14         {
15             int v=e[i].v, w=e[i].w;
16             dfs(v,dep+1);
17             ver[++tot]=u;      //回溯
18             deep[tot]=dep;
19         }
20     }
21 }      

接下來是ST算法，也就是RMQ，計算出所有的d[i][j]。

1 void ST(int n)
 2 {
 3     for(int i=1;i<=n;i++)  dp[i][0]=i;
 4     for(int j=1;(1<<j)<=n;j++)
 5         for(int i=1;i+(1<<j)-1<=n;i++)
 6         {
 7             int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
 8             dp[i][j]=deep[a]<deep[b]?a:b;
 9         }
10 }      

1 int LCA(int u, int v)
2 {
3     int x=first[u], y=first[v];   //查找出他最先出現的地方
4     if(x>y)  swap(x,y);
5     int res=RMQ(x,y);    //查詢出的是他祖先的下标
6     return ver[res];   
7 }