最近公共祖先(LCA)问题

最近公共祖先问题为对于一棵树中两个结点 u 和 v。 找一个结点 x 为 u 和 v 的公共祖先，并且使得 x 结点在树中的深度最大， x 就是 u 和 v 的最近公共祖先。

 

解决最近公共祖先问题一般有两种方法。

1).  Tarjan 的脱机最小公共祖先算法

这个算法基于并查集和深度优先搜索。算法从根开始，对每一棵子树进行深度优先搜索，访问根时，将创建由根结点构建的集合，然后对以他的孩子结点为根的子树进行搜索，使对于 u， v 属于其某一棵子树的 LCA 询问完成。这时将其所有子树结点与根结点合并为一个集合。 对于属于这个集合的结点 u, v 其 LCA 必定是根结点。

算法伪码：

LCA(u){
    MAKE_SET(u)
    ancestor[FIND(u)]= u
    for( each child v of u ){
        LCA(v)
        UNION(u,v)
        ancestor[FIND(u)]=u
    }
    flag[u]= 1;
    for( each node v such that [u,v] in P )
    if( flag[v] )
    print "The least common ancestor of 'u' and 'v' is " ancestor[ FIND(v) ]
}

POJ 1330 Nearest Common Ancestors

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

#define N 10010

vector<int> map[N];
int n, uset[N], ancestor[N], u, v, flag[N], deg[N], root;

int find( int x ){
    while( uset[x] ) x= uset[x];
    return x;
}

void Union( int x, int y ){
    int a= find(x), b= find(y);
    uset[a]= b; }
    
void LCA( int x ){
    uset[x]= x; ancestor[x]= x;
    for( size_t i= 0; i< map[x].size(); ++i ){
        int y= map[x][i];
        LCA( y );
        
        Union( x, y );
        ancestor[ find(y) ]= x;
    }
    flag[x]= 1;
    if( x== u && flag[v] ){
        printf("%d\n", ancestor[ find(v) ] );
        return; }
    else if( x== v && flag[u] ){
        printf("%d\n", ancestor[ find(u) ] );
        return; }
}

int main(){
    int test;
    scanf("%d",&test );
    while( test-- ){
        scanf("%d",&n);
        
        for( int i= 0; i<= n; ++i ) { ancestor[i]= 0; flag[i]= 0; deg[i]= 0; }
        for( int i= 1; i< n; ++i ){
            int x, y;
            scanf("%d%d", &x, &y);
            map[x].push_back(y);
            deg[y]++;
        }
        scanf("%d%d",&u,&v);
        for( int i= 1; i<= n; ++i )
        if( deg[i]== 0 ) root= i;
    
        LCA( root );
        for( int i= 0; i<= n; ++i ) map[i].clear();
    }
    
    return 0;
}

2). 转换为 RMQ 问题。

将有向树看成无向树，对于 u 和 v 的最近公共主祖先，则可以证明，最近公共祖先必定在 u 通往 v 的最短路径上，并且是最短路径上深度最小的结点。先对树进行 DFS， 保存其 DFS 序列， 再在序列找深度最小的结点。

 

例如：

对于树 , V= { 1, 2, 3, 4, 5 }, E= { <1,2>, <1,3>, <3,4>, <3,5> }

对其进行 DFS 访问，记录的一种 DFS 访问路径为( 用E[]记录 ):

E[i]: 1 2 1 3 4 3 5 3 1       对应的结点在树中的深度为( 用D[]记录 )：

D[i]: 0 1 0 1 2 1 2 1 0

 

对于求 u 和 v 的最近公共祖先，先找到 u 和 v 在E[]中第一次出现的位置， 如 u= 2, v= 3 时， 2 在 E[] 中第一次出现的位置在 E[] 中下标为 1， 3第一次有 E[] 中出现的下标为 3, 考虑 E[] 中，下标从 1 到 3 这一段， { 2, 1, 3 } 对应深度为 { 1, 0, 1 } 深度最小为 0, 对应的结点为 1, 所以 u= 2, v= 3 的最近公共祖先为 1。

 

对一个数组中某一段求最值可以用 RMQ 来做，所以 LCA 问题就转化为了 RMQ 问题了。

 

Pku 1470 采用转化成 RMQ 问题的方法解决

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
#define N 902

int n, m;
vector<int> map[N];
int E[N<<1], D[N<<1], R[N], flag[N], Min[N<<1][12], cnt, rt;

void dfs( int x, int h ){
    E[++cnt]= x; D[cnt]= h;
    if( !flag[x] ){ R[x]= cnt; flag[x]= 1; }
    
    for( size_t i= 0; i< map[x].size(); ++i ){
        int v= map[x][i];
        
        if( flag[v]== 0 ) dfs( v, h+ 1 );
        E[++cnt]= x; D[cnt]= h;
    }
}

void init(){
    for( int i= 1; i<= cnt; ++i ) Min[i][0]= i;
    for( int i= 1; 1<<i< cnt; i++ )
    for( int j= 0, s= 1<< (i-1); j+ s< cnt; j++ ){
        if( D[ Min[j][i-1] ]< D[ Min[j+ s][i-1] ] )Min[j][i]= Min[j][i-1];
        else Min[j][i]= Min[j+s][i-1];
    }
}

int rmq( int x, int y ){
    if( x> y ) x^= y^= x^= y;
    int d= y- x+ 1, t= 0;
    while( 1<<t <= d ) t++; t--;
    if( D[ Min[x][t] ]< D[ Min[y-(1<<t)+1][t] ] ) return Min[x][t];
    else return Min[y-(1<<t)+1][t];
}

int main(){
    while( scanf("%d",&n)!= EOF ){
        for( int i= 0; i<= n; ++i ) flag[i]= 0;
        cnt= 0;
        
        for( int i= 1; i<= n; ++i ){
            int u, num, v;
            scanf("%d",&u);
            while( getchar()!= '(');
            scanf("%d",&num);
            while( getchar()!= ')');
            
            while( num-- ){
                scanf("%d",&v );
                map[u].push_back(v); flag[v]++;
            }
        }
        
        for( int i= 1; i<= n; ++i )
        if( flag[i]== 0 ){ rt= i; break; }
        
        for( int i= 0; i<= n; ++i ) flag[i]= 0;
        dfs( rt, 0 );
        init();
        
        for( int i= 0; i<= n; ++i ) flag[i]= 0;
        scanf("%d",&m );
        for( int i= 1; i<= m; ++i ){
            while( getchar()!= '(' );
            int u, v;
            scanf("%d%d", &u, &v );
            
            int pos= rmq( R[u], R[v] );
            flag[ E[pos] ]++;
            while( getchar()!= ')' );
        }
        
        for( int i= 1; i<= n; ++i )
        if( flag[i] ) printf("%d:%d\n", i, flag[i] );
        
        for( int i= 0; i<= n; ++i ) map[i].clear();
    }
    return 0;
}