The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

導(dǎo)航

<

2010年12月

>

日

一

二

三

四

五

六

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

統(tǒng)計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

搜索

閱讀排行榜

評論排行榜

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

關(guān)于LCA和RMQ問題

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

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

這里給出一個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

二、RMQ問題(Range Minimum Query)

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

例二

對數(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)化方法。

對樹進(jìn)行深度優(yōu)先遍歷，每當(dāng)“進(jìn)入”或回溯到某個結(jié)點(diǎn)時，將這個結(jié)點(diǎn)的深度存入數(shù)組E最后一位。同時記錄結(jié)點(diǎn)i在數(shù)組中第一次出現(xiàn)的位置(事實(shí)上就是進(jìn)入結(jié)點(diǎn)i時記錄的位置)，記做R[i]。如果結(jié)點(diǎn)E[i]的深度記做D[i]，易見，這時求LCA(T,u,v)，就等價于求E[RMQ(D,R[u],R[v])]，(R[u]<R[v])。例如，對于第一節(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ù)很水，但是算法絕對經(jīng)典，題目要求兩個節(jié)點(diǎn)的最近公共祖先，這個tarjan算法使用了并查集+dfs的操作。這個算法研究了我兩個小時，開始的時候在網(wǎng)上查找資料，寫的都不盡人意，看不明白，后來干脆直接看代碼，模擬了一遍，搞懂了。。。看來計算機(jī)的世界，只有代碼才是王道！中間的那個并查集操作的作用，只是將已經(jīng)查找過的節(jié)點(diǎn)捆成一個集合然后再指向一個公共的祖先。另外，如果要查詢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)系，耗時47MS,也許改成單純的鏈表要更好些；
還有就是，如果這個樹的根節(jié)點(diǎn)不確定，邊沒有方向可言的話，又應(yīng)該如何做呢？（找不到根了。。。）
如果要找兩個節(jié)點(diǎn)之間的一條通路又該怎么辦？
看來，這個問題還有繼續(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;

}

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

——————————————————傳說中的分割線——————————————————————————————————
終于用RMQ過了，起初一直RE,原來是RM Q里面的數(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;

/**/////遞推計算狀態(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

{

/**///// 用對2去對數(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) 評論(1) 編輯收藏引用

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

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

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

評論

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




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