The Fourth Dimension Space

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

統計

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

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

關于LCA和RMQ問題

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

對于有根樹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

二、RMQ問題(Range Minimum Query)

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

例二

對數列：5,8,1,3,6,4,9,5,7 有：

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

RMQ問題與LCA問題的關系緊密，可以相互轉換，相應的求解算法也有異曲同工之妙。

下面給出LCA問題向RMQ問題的轉化方法。

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

數列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

易知，轉化后得到的數列長度為樹的結點數的兩倍加一，所以轉化后的RMQ問題與LCA問題的規模同次

數據很水，但是算法絕對經典，題目要求兩個節點的最近公共祖先，這個tarjan算法使用了并查集+dfs的操作。這個算法研究了我兩個小時，開始的時候在網上查找資料，寫的都不盡人意，看不明白，后來干脆直接看代碼，模擬了一遍，搞懂了。。。看來計算機的世界，只有代碼才是王道！中間的那個并查集操作的作用，只是將已經查找過的節點捆成一個集合然后再指向一個公共的祖先。另外，如果要查詢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];

}//查找函數，并壓縮路徑

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;

}//合并函數，如果屬于同一分支則返回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的關系，耗時47MS,也許改成單純的鏈表要更好些；
還有就是，如果這個樹的根節點不確定，邊沒有方向可言的話，又應該如何做呢？（找不到根了。。。）
如果要找兩個節點之間的一條通路又該怎么辦？
看來，這個問題還有繼續研究下去的必要。。。

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

#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];

}//查找函數，并壓縮路徑

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;

}//合并函數，如果屬于同一分支則返回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;

}

汗，寫了個指針版運行速度居然比vector還慢，太打擊我對指針的信心了。。。可能是數據太弱了吧，指針的優勢沒有發揮出來。。。

——————————————————傳說中的分割線——————————————————————————————————
終于用RMQ過了，起初一直RE,原來是RM Q里面的數組開小了。。。不過感覺時間效率不是很高，110MS，應該是詢問的次數太少的原因吧。
RMQ應付的應該是詢問次數非常巨大的情況。而且它是在線的算法，可以按順序輸出結果，這樣才能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)//預處理

{

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

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

/**/////初始狀態

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

fij[i][0] = 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去對數的方法求出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數組

{

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

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

評論

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




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理