LCA問題
給定一棵有根樹T,對于任意兩個(gè)節(jié)點(diǎn)u,v，求出LCA(T,u,v)
LCA的tarjan算法 （離線算法）
//初始所有節(jié)點(diǎn)color為WHITE
void LCA(u)
{
MAKE_SET(u);
ancester[FIND_SET(u)]=u;
for(u的每個(gè)兒子v)
{
LCA(v);
UNION(u,v);
ancester[FIND_SET(u)]=u;
}
color[u]=BLACK
for(Q(u)中的所有元素)
{
if(color[v]==BLACK)
printf("LCA(%d,%d)=%d\n",u,v,ancester[FIND_SET(v)]);
}
}
MAKE_SET(u)表示建立一個(gè)只有u的集合，且u為集合的代表元
FIND_SET(u)表示找出集合的代表元
UNION(u,v) 表示合并u,v所在的集合
RMQ問題
給定一個(gè)長度為n的數(shù)組n，回答詢問RMQ(A,i,j)，即A[i..j]中元素最小的數(shù)的下標(biāo)
將LCA問題轉(zhuǎn)化為RMQ問題
1.DFS遍歷樹，記錄遍歷到的節(jié)點(diǎn)E[1..2n-1],
并用R[i]表示E數(shù)組中第一個(gè)值為i的元素的下標(biāo)
2.對于任意 R[u]<R[v] ,dfs中第一次訪問u到第一次訪問v的路徑是E[R[u]..R[v]]
并且其中深度最小的節(jié)點(diǎn)一定是u,v的LCA
3.令數(shù)組L[i]表示節(jié)點(diǎn)E[i]的深度，那么當(dāng)R[u]<R[v]時(shí)，LCA(T,u,v)=RMQ(L,R[u],R[v]);
轉(zhuǎn)換后的RMQ問題比較特殊，相鄰兩個(gè)元素的相差1或-1，這樣的問題成為+_1-RMQ
一般RMQ的Spare Table(ST) 算法
d[i,j]表示從i開始長度為2^j的區(qū)間的RMQ，
則有遞推公式 d[i,j]=min(d[i][j-1],d[i+2^(j-1),j-1]),即用兩個(gè)相鄰的長度為2^(j-1)
的區(qū)間來分形長度為2^j的區(qū)間 預(yù)處理時(shí)間復(fù)雜度為O(nlogn)
詢問時(shí) 取k=log2(j-i+1)令A(yù)為從i開始的長度為2^k的塊的RMQ
令B為到j(luò)結(jié)束的長度為2^k的塊的RMQ
則RMQ(i,j)=min(A,B),
即 k=log2(j-i+1),RMQ[i,j]=min(d[i,k],d[j-2^k+1,k])
+_1-RMQ的O(n)-O(1)算法
………………………………
未完待續(xù)…………
////////
寫了個(gè)lca的代碼
不知道對不對
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 505
#define black 1
#define white 0
int father[maxn],ancester[maxn];
int color[maxn];
struct node
{
int v,next;
} edge[maxn*maxn];
int p[maxn];
int n,e,m;
int root;
void add(int u,int v)
{
edge[e].v=v;
edge[e].next=p[u];
p[u]=e++;
}
int find(int u)
{
if (u==father[u]) return u;
else
{
father[u]=find(father[u]);
}//路徑壓縮
return father[u];
}
void union1(int u,int v)
{
int tmp,tmp1;
tmp=find(u);
tmp1=find(v);
father[tmp1]=tmp;
}
void lca(int u)
{
int i,v,v1;
father[u]=u;
ancester[find(u)]=u;
for(i=p[u]; i!=-1; i=edge[i].next)
{
v=edge[i].v;
lca(v);
union1(u,v);
ancester[find(u)]=u;
}
/*for(i=p1[u]; i!=-1; i=edge1[i].next)
{
v1=edge1[i].v;
if (color[v1]==black)
printf("LCA(%d,%d)=%d\n",u,v1,ancester[find(v)]);
}*/
color[u]=black;
for(i=1;i<=n;i++)
if(i!=u)
{
if (color[i]==black)
{
printf("LCA(%d,%d)=%d\n",u,i,ancester[find(i)]);
}
}
}
int main()
{
int a,b,i;
scanf("%d%d",&n,&m);
scanf("%d",&root);
memset(p,-1,sizeof(p));
e=0;
for(i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
for(i=1; i<=n; i++) father[i]=i;
memset(color,white,sizeof(color));
lca(1);
return 0;
}