The Fourth Dimension Space

一、最近公共祖先(Least Common Ancestors)

對(duì)于有根樹T的兩個(gè)結(jié)點(diǎn)u、v，最近公共祖先LCA(T,u,v)表示一個(gè)結(jié)點(diǎn)x，滿足x是u、v的祖先且x的深度盡可能大。另一種理解方式是把T理解為一個(gè)無向無環(huán)圖，而LCA(T,u,v)即u到v的最短路上深度最小的點(diǎn)。

這里給出一個(gè)LCA的例子：

例一

對(duì)于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

二、RMQ問題(Range Minimum Query)

RMQ問題是指：對(duì)于長度為n的數(shù)列A，回答若干詢問RMQ(A,i,j)(i,j<=n)，返回?cái)?shù)列A中下標(biāo)在[i,j]里的最小值下標(biāo)。這時(shí)一個(gè)RMQ問題的例子：

例二

對(duì)數(shù)列：5,8,1,3,6,4,9,5,7 有：

RMQ(2,4)=3
RMQ(6,9)=6

RMQ問題與LCA問題的關(guān)系緊密，可以相互轉(zhuǎn)換，相應(yīng)的求解算法也有異曲同工之妙。

下面給出LCA問題向RMQ問題的轉(zhuǎn)化方法。

對(duì)樹進(jìn)行深度優(yōu)先遍歷，每當(dāng)“進(jìn)入”或回溯到某個(gè)結(jié)點(diǎn)時(shí)，將這個(gè)結(jié)點(diǎn)的深度存入數(shù)組E最后一位。同時(shí)記錄結(jié)點(diǎn)i在數(shù)組中第一次出現(xiàn)的位置(事實(shí)上就是進(jìn)入結(jié)點(diǎn)i時(shí)記錄的位置)，記做R[i]。如果結(jié)點(diǎn)E[i]的深度記做D[i]，易見，這時(shí)求LCA(T,u,v)，就等價(jià)于求E[RMQ(D,R[u],R[v])]，(R[u]<R[v])。例如，對(duì)于第一節(jié)的例一，求解步驟如下：

數(shù)列E[i]為：1,2,1,3,4,3,5,3,1
R[i]為：1,2,4,5,7
D[i]為：0,1,0,1,2,1,2,1,0

于是有：

LCA(T,5,2) = E[RMQ(D,R[2],R[5])] = E[RMQ(D,2,7)] = E[3] = 1
LCA(T,3,4) = E[RMQ(D,R[3],R[4])] = E[RMQ(D,4,5)] = E[4] = 3
LCA(T,4,5) = E[RMQ(D,R[4],R[5])] = E[RMQ(D,5,7)] = E[6] = 3

易知，轉(zhuǎn)化后得到的數(shù)列長度為樹的結(jié)點(diǎn)數(shù)的兩倍加一，所以轉(zhuǎn)化后的RMQ問題與LCA問題的規(guī)模同次

數(shù)據(jù)很水，但是算法絕對(duì)經(jīng)典，題目要求兩個(gè)節(jié)點(diǎn)的最近公共祖先，這個(gè)tarjan算法使用了并查集+dfs的操作。這個(gè)算法研究了我兩個(gè)小時(shí)，開始的時(shí)候在網(wǎng)上查找資料，寫的都不盡人意，看不明白，后來干脆直接看代碼，模擬了一遍，搞懂了。。。看來計(jì)算機(jī)的世界，只有代碼才是王道！中間的那個(gè)并查集操作的作用，只是將已經(jīng)查找過的節(jié)點(diǎn)捆成一個(gè)集合然后再指向一個(gè)公共的祖先。另外，如果要查詢LCA(a,b)，必須把(a,b)和(b,a)都加入鄰接表。

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

using namespace std;

#define MAX 10001

int f[MAX];

int r[MAX];

int indegree[MAX];

int visit[MAX];

vector<int> hash[MAX],Qes[MAX];

int ancestor[MAX];

void init(int n)

{

int i;

for(i=1;i<=n;i++)

{

r[i]=1;

f[i]=i;

indegree[i]=0;

visit[i]=0;

ancestor[i]=0;

hash[i].clear();

Qes[i].clear();

}

int find(int n)

{

if(f[n]==n)

return n;

else

f[n]=find(f[n]);

return f[n];

}//查找函數(shù)，并壓縮路徑

int Union(int x,int y)

{

int a=find(x);

int b=find(y);

if(a==b)

return 0;

else if(r[a]<=r[b])

{

f[a]=b;

r[b]+=r[a];

}

else

{

f[b]=a;

r[a]+=r[b];

}

return 1;

}//合并函數(shù)，如果屬于同一分支則返回0，成功合并返回1

void LCA(int u)

{

ancestor[u]=u;

int i,size = hash[u].size();

for(i=0;i<size;i++)

{

LCA(hash[u][i]);

Union(u,hash[u][i]);

ancestor[find(u)]=u;

}

visit[u]=1;

size = Qes[u].size();

for(i=0;i<size;i++)

{

if(visit[Qes[u][i]]==1)

{

printf("%d\n",ancestor[find(Qes[u][i])]);

return;

}

int main()

{

int testcase;

int n;

int i,j;

scanf("%d",&testcase);

for(i=1;i<=testcase;i++)

{

scanf("%d",&n);

init(n);

int s,t;

for(j=1;j<=n-1;j++)

{

scanf("%d%d",&s,&t);

hash[s].push_back(t);

indegree[t]++;

}

scanf("%d%d",&s,&t);

Qes[s].push_back(t);

Qes[t].push_back(s);

for(j=1;j<=n;j++)

{

if(indegree[j]==0)

{

LCA(j);

break;

}

return 0;

}

不過可能是用了vector的關(guān)系，耗時(shí)47MS,也許改成單純的鏈表要更好些；
還有就是，如果這個(gè)樹的根節(jié)點(diǎn)不確定，邊沒有方向可言的話，又應(yīng)該如何做呢？（找不到根了。。。）
如果要找兩個(gè)節(jié)點(diǎn)之間的一條通路又該怎么辦？
看來，這個(gè)問題還有繼續(xù)研究下去的必要。。。

———————————————————————傳說中的分割線——————————————————————————
指針版：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

using namespace std;

#define MAX 10001

struct node

{

int a;

node *next;

}hash[MAX];

node Qes[MAX];

void Add(node hash[],int a,int b)

{

node *p=&hash[a];

node *q=p->next;

node *r=new node;

r->a=b;

p->next=r;

r->next=q;

}

int f[MAX];

int r[MAX];

int indegree[MAX];

int visit[MAX];

int ancestor[MAX];

void init(int n)

{

int i;

for(i=1;i<=n;i++)

{

r[i]=1;

f[i]=i;

indegree[i]=0;

visit[i]=0;

ancestor[i]=0;

hash[i].next=NULL;

Qes[i].next=NULL;

}

int find(int n)

{

if(f[n]==n)

return n;

else

f[n]=find(f[n]);

return f[n];

}//查找函數(shù)，并壓縮路徑

int Union(int x,int y)

{

int a=find(x);

int b=find(y);

if(a==b)

return 0;

else if(r[a]<=r[b])

{

f[a]=b;

r[b]+=r[a];

}

else

{

f[b]=a;

r[a]+=r[b];

}

return 1;

}//合并函數(shù)，如果屬于同一分支則返回0，成功合并返回1

void LCA(int u)

{

ancestor[u]=u;

node *p;

for(p=hash[u].next;p!=NULL;p=p->next)

{

LCA(p->a);

Union(u,p->a);

ancestor[find(u)]=u;

}

visit[u]=1;

for(p=Qes[u].next;p!=NULL;p=p->next)

{

if(visit[p->a]==1)

{

printf("%d\n",ancestor[find(p->a)]);

return;

}

int main()

{

int testcase;

int n;

int i,j;

scanf("%d",&testcase);

for(i=1;i<=testcase;i++)

{

scanf("%d",&n);

init(n);

int s,t;

for(j=1;j<=n-1;j++)

{

scanf("%d%d",&s,&t);

Add(hash,s,t);

indegree[t]++;

}

scanf("%d%d",&s,&t);

Add(Qes,s,t);

Add(Qes,t,s);

for(j=1;j<=n;j++)

{

if(indegree[j]==0)

{

LCA(j);

break;

}

return 0;

}

汗，寫了個(gè)指針版運(yùn)行速度居然比vector還慢，太打擊我對(duì)指針的信心了。。。可能是數(shù)據(jù)太弱了吧，指針的優(yōu)勢(shì)沒有發(fā)揮出來。。。

——————————————————傳說中的分割線——————————————————————————————————
終于用RMQ過了，起初一直RE,原來是RM Q里面的數(shù)組開小了。。。不過感覺時(shí)間效率不是很高，110MS，應(yīng)該是詢問的次數(shù)太少的原因吧。
RMQ應(yīng)付的應(yīng)該是詢問次數(shù)非常巨大的情況。而且它是在線的算法，可以按順序輸出結(jié)果，這樣才能AC題目啊。

#include<iostream>

#include<math.h>

#include<vector>

using namespace std;

vector<int>hash[10001];//用vector代替鄰接表

#define MAXN 10001

#define mmin(seq, a, b) ((seq[a] < seq[b]) ? (a) : (b))

int indegree[MAXN];

/**///// DP status

int fij[100000][100];

template <typename T>

void st(T seq[], int n)//預(yù)處理

{

memset(fij, 0, 100 * MAXN * sizeof(int));

int k = (int)(log((double)n) / log(2.0));

/**/////初始狀態(tài)

for(int i = 0; i < n; i++)

fij[i][0] = i;

/**/////遞推計(jì)算狀態(tài)

for(int j = 1; j <= k; j++)

{

for(int i = 0; i + (1 << j) - 1 < n; i++)

{

//

int m = i + (1 << (j - 1));

//fij[i][j] = seq[fij[i][j - 1]] < seq[fij[m][j - 1]] ? fij[i][j - 1] : fij[m][j - 1];

fij[i][j] = mmin(seq, fij[i][j - 1], fij[m][j - 1]);

}

template <typename T>

int RMQ(T seq[], int i, int j)//求解RMQ

{

/**///// 用對(duì)2去對(duì)數(shù)的方法求出k

int k = (int)(log(double(j - i + 1)) / log(2.0));

/**/////

//int t = seq[fij[i][k]] < seq[fij[j - (1 << k) + 1][k]] ? fij[i][k] : fij[j - (1 << k) + 1][k];

int t = mmin(seq, fij[i][k], fij[j - (1 << k) + 1][k]);

return t;

}

int E[MAXN*2+1];

int R[MAXN*2+1];

int D[MAXN*2+1];

int p=0;

void dfs(int r,int deep)//深搜，算出E,R,D數(shù)組

{

p++;

E[p]=r;

D[p]=deep;

R[r]=p;

int i;

int size=hash[r].size();

for(i=0;i<size;i++)

{

dfs(hash[r][i],deep+1);

p++;

E[p]=r;

D[p]=deep;

}

int main()

{

int testcase;

int n;

int i,j;

int s,t;

scanf("%d",&testcase);

for(i=1;i<=testcase;i++)

{

scanf("%d",&n);

for(j=1;j<=n;j++)

{

indegree[j]=0;

hash[j].clear();

}

p=0;

for(j=1;j<n;j++)

{

int a,b;

scanf("%d%d",&a,&b);

hash[a].push_back(b);

indegree[b]++;

}

scanf("%d%d",&s,&t);

int root;

for(j=1;j<=n;j++)

{

if(indegree[j]==0)

{

root=j;

break;

}

dfs(root,0);

st(D,2*n+2);

if(R[s]<R[t])

printf("%d\n",E[ RMQ(D,R[s],R[t]) ] );

else

printf("%d\n",E[ RMQ(D,R[t],R[s]) ] );

}

return 0;

}

posted on 2009-09-21 22:24 abilitytao 閱讀(3573) 評(píng)論(1) 編輯收藏引用

評(píng)論

# re: POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)[未登錄] 2009-09-22 16:08 vincent

神牛平均一天切幾題啊..速度很汗顏啊回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)[未登錄] 2009-09-22 16:08 vincent

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

評(píng)論