LCA
簡介
對於有根樹T的兩個結點u、v，最近公共祖先LCA(T,u,v)表示一個結點x，滿足x是u、v的祖先且x的深度儘可能大。另一種理解方式是把T理解為一個無向無環圖，而LCA(T,u,v)即u到v的最短路上深度最小的點。
這裡給出一個LCA的例子：
對於T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}
則有：
LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3
LCA問題算法
1.離線算法tarjan
利用並查集優越的時空複雜度，我們可以實現LCA問題的O(n+Q)算法，這裡Q表示詢問的次數。tarjan算法基於深度優先搜尋的框架，對於新搜尋到 的一個結點，首先創建由這個結點構成的集合，再對當前結點的每一個子樹進行搜尋，每搜尋完一棵子樹，則可確定子樹內的LCA詢問都已解決。其他的LCA詢 問的結果必然在這個子樹之外，這時把子樹所形成的集合與當前結點的集合合併，並將當前結點設為這個集合的祖先。之後繼續搜尋下一棵子樹，直到當前結點的所 有子樹搜尋完。這時把當前結點也設為已被檢查過的，同時可以處理有關當前結點的LCA詢問，如果有一個從當前結點到結點v的詢問，且v已被檢查過，則由於 進行的是深度優先搜尋，當前結點與v的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包涵v的子樹一定已經搜尋過了，那么這個最近公共祖先一定是v 所在集合的祖先。
下面給出這個算法的偽代碼描述：
LCA(u) {
Make-Set(u)
ancestor[Find-Set(u)]=u
對於u的每一個孩子v {
LCA(v)
Union(u)
ancestor[Find-Set(u)]=u
}
checked[u]=true
對於每個(u,v)屬於P {
if checked[v]=true
then 回答u和v的最近公共祖先為 ancestor[Find-Set(v)]
}
}
由於是基於深度優先搜尋的算法，只要調用LCA(root[T])就可以回答所有的提問了，這裡root[T]表示樹T的根，假設所有詢問(u,v)構成集合P。
2.線上算法 倍增法
每次詢問O(logN)
d[i] 表示 i節點的深度, p[i,j] 表示 i 的 2^j 倍祖先
那么就有一個遞推式子 p[i,j]=p[p[i,j-1],j-1]
這樣子一個O(NlogN)的預處理求出每個節點的 2^k 的祖先
然後對於每一個詢問的點對a, b的最近公共祖先就是：
先判斷是否 d[a] > d[b] ,如果是的話就交換一下(保證 a 的深度小於 b 方便下面的操作)然後把b 調到與a 同深度, 同深度以後再把a, b 同時往上調(dec(j)) 調到有一個最小的j 滿足p[a,j]!=p[b,j] (a b 是在不斷更新的), 最後再把 a, b 往上調 (a=p[a,0], b=p[b,0]) 一個一個向上調直到a = b, 這時 a or b 就是他們的最近公共祖先
實例算法
問題描述：
設計一個算法，對於給定的樹中2 結點返回它們的最近公共祖先。
編程任務：
對於給定的樹，和樹中結點對，編程計算結點對的最近公共祖先。
數據輸入：
由檔案input.txt給出輸入數據。第一行有1個正整數n，表示給定的樹有n個頂點，編
號為1，2，…，n。編號為1 的頂點是樹根。接下來的n 行中，第i+1 行描述與i 個頂點相關聯的子結點的信息。每行的第一個正整數k表示該頂點的兒子結點數。其後k個數中，每1 個數表示1 個兒子結點的編號。當k=0 時表示相應的結點是葉結點。檔案的第n+2 行是1 個正整數m，表示要計算最近公共祖先的m個結點對。接下來的m行，每行2 個正整數，是要計算最近公共祖先的結點編號。
結果輸出:
將編程計算出的m個結點對的最近公共祖先結點編號輸出到檔案output.txt。每行3 個
正整數，前2 個是結點對編號，第3 個是它們的最近公共祖先結點編號。
輸入檔案示例 輸出檔案示例
input.txt
12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10
output.txt
3 11 1
7 12 2
4 8 1
9 12 6
8 10 2
#include<iostream>
#include<fstream>
using namespace std;
/********************快速排序****************************************/
inline void Swap(int &a, int &b)
{
int temp=a;
a=b;
b=temp;
}///:p
int Partition(int *a, int p, int r)
{
int i=p;
int j=r+1;
int x=a[p];
while(true)
{
while(a[++i]<x&&i<r);
while(a[--j]>x);
if(i>=j)
{
break;
}
Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}///:p
void QuickSort(int *a, int p, int r)
{
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}///:p
/*******************************************************************/
/***************二分法查找******************************************/
int FindSource(int *array, int source, int low, int high)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(source==array[mid])
{
return source;
}
else
{
if(source<array[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
}
return -1;
}///:p
/*******************************************************************/
class CommonTree
{
public:
CommonTree(int Max=10);
~CommonTree();
void getdata(int *treedata,int num);
int find_same_ancestor(int Node1, int Node2, int array_num);
void getroot(int i);
int Size();
void Print() const;
private:
int *TreeArray;
int size;
int root;
};///:p
CommonTree::CommonTree(int Max)
{
size=Max;
TreeArray=new int [size];
if(TreeArray==NULL)
{
exit(1);
}
}///:p
CommonTree::~CommonTree()
{
delete [] TreeArray;
}///:p
void CommonTree::getdata(int *treedata,int num)
{
int *p_temp=TreeArray;
TreeArray=treedata;
treedata=p_temp;
size=num;
delete [] treedata;
treedata=NULL;
}///:p
int CommonTree::find_same_ancestor(int Node1,int Node2, int array_num)
{
int *array_Node1=new int [array_num];
int *array_Node2=new int [array_num];
if(array_Node1==NULL&&array_Node2==NULL)
{
exit(1);
}
int x=Node1, array_Node1_num=0;
array_Node1[0]=x;
while(x!=root)
{
x=TreeArray[x];
array_Node1_num++;
array_Node1[array_Node1_num]=x;
}
x=Node2;
int array_Node2_num=0;
array_Node2[0]=x;
while(x!=root)
{
x=TreeArray[x];
array_Node2_num++;
array_Node2[array_Node2_num]=x;
}
QuickSort(array_Node2, 0, array_Node2_num);
int result=0;
for(int i=0; i<=array_Node1_num; i++)
{
result=FindSource(array_Node2, array_Node1[i], 0, array_Node2_num);
if(result!=-1)
{
break;
}
}
delete []array_Node1;
delete []array_Node2;
return result;
}///:p
inline int CommonTree::Size()
{
return size;
}///:p
inline void CommonTree::getroot(int i)
{
root=i;
}///:p
void CommonTree::Print() const
{
for(int i=1;i<size;i++)
{
cout<<this->TreeArray[i]<<" ";
}
cout<<endl;
cout<<root<<endl;
}///:p
int main()
{
ifstream in("input.txt");
if(in.fail())
{
cout<<"input error!"<<endl;
exit(1);
}
ofstream out("output.txt");
int NodeNum;
in>>NodeNum;
int *AncestorTree=new int [NodeNum+1];
if(AncestorTree==NULL)
{
exit(1);
}
memset(AncestorTree, 0, sizeof(int)*(NodeNum+1));
int father=1;
for(int j=0; j<NodeNum; j++)
{
int lop;
in>>lop;
for(int i=0;i<lop;i++)
{
int temp;
in>>temp;
AncestorTree[temp]=father;
}
father++;
}
for(j=1; j<=NodeNum;j++)
{
if(AncestorTree[j]==0)
{
AncestorTree[j]=j;
break;
}
}
int find_num;
in>>find_num;
int *result=new int [3*find_num];
if(result==NULL)
{
exit(1);
}
for(int i=0; i<2*find_num; i++)
{
in>>result[i];
}
CommonTree main_tree(10);
main_tree.getdata(AncestorTree,NodeNum+1);
main_tree.getroot(j);
int displace=0;
for(i=0; i<find_num; i++)
{
result[2*find_num+i]=main_tree.find_same_ancestor(result[displace], result[displace+1], NodeNum);
displace+=2;
}
displace=0;
for(i=0; i<find_num; i++)
{
out<<result[displace]<<" "<<result[displace+1]<<" "<<result[2*find_num+i];
displace+=2;
out<<endl;
}
delete [] result;
return 0;
}
c++代碼實現
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
#define max_size 1010
int d[max_size], p[max_size][10];
int head[max_size];
int cnt;
//構造樹時用到的機構體，看過一個大牛用的，感覺很好
struct Edge
{
int v;
int pre;
}eg[max_size];
//建樹的函式
void add(int x, int y)
{
eg[cnt].v = y;
eg[cnt].pre = head[x];
head[x] = cnt++;
}
//dfs()初始整顆數，算出d[1-n], p[1-n][j];
void dfs(int k)
{
if (head[k] == 0)
{
return ;
}
int m, x, i, j;
for (i = head[k]; i != 0; i = eg[i].pre)
{
x = eg[i].v;
p[x][0] = k;
m = k;
d[x] = d[k]+1;
for (j = 0; p[m][j] != 0; j++)
{
p[x][j+1] = p[m][j]; //利用公式 p[x][j] = p[p[x][j-1]][j-1],這裡的m就是p[x][j-1];
m = p[m][j];
}
dfs(x);
}
}
int find_lca(int x, int y)
{
int m, k;
if (x == y)return x;
if (d[x] < d[y])
{
m = x;
x = y;
y = m;
}
m = d[x] - d[y];
k = 0;
while (m)
//將x的深度調到和y的深度一樣
{
if (m&1)
x = p[x][k];
m >>= 1;
k++;
}
if (x == y)return x;
k = 0;
// 向上調節，找最近公共祖先， 算法的核心，相當於一個二分查找。
while (x != y)
{
if (p[x][k] != p[y][k] || p[x][k] == p[y][k] && k == 0)
//如果p[x][k]還不相等，說明節點p[x][k]還在所求點的下面，所以繼續向上調節
//如果相等了，並且就是他們父節點，則那個節點一定就是所求點。
{
x = p[x][k];
y = p[y][k];
k++;
}
else//如果p[x][k] = p[y][k],可以說明p[x][k]一定是x和y的共祖先，但不一定是最近的。
//所以向下找看還有沒有更近的公共祖先
{
k--;
}
}
return x;
}
int main()
{
int i, n, m, x, y;
while (cin >> n >> m)
{
memset(head, 0, sizeof(head));
memset(p, 0, sizeof(p));
memset(d, 0, sizeof(d));
cnt = 1;
for (i = 2; i <= n; i++)
{
scanf("%d", &x);
add(x, i);
}
dfs(1);
for (i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
printf("%d/n", find_lca(x, y));
}
}
return 0;
}
