3

LCA最近公共祖先 - little_sheep_xiaoen

 2 years ago
source link: https://www.cnblogs.com/xiao-en/p/16460460.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

LCA最近公共祖先

最近公共祖先就字面意思，两个节点一起往上跳，找到的最近的公共点

找到u和v第一个不同祖先不同的位置，然后这个位置向上走一步就是最近公共的祖先

但是想找到u,v第一个不同祖先的位置，就要保证u,v在同一深度（才能一起往上移动）

所以这个过程分为三部分，

　　1. 预处理找到每个节点深度

　　2. 把较深的一点移动到较浅一点的高度

　　3. 两个一起往上移动直到他们的父亲相同

预处理找深度

这里找深度可以用一个deepdeep数组存下，用bfsbfs找到所有深度，顺便可以把父节点也记录了

ContractedBlock.gifExpandedBlockStart.gif

BFS找深度与父节点

找公共祖先

在两点跳到同样深度后，有两种做法

　　（一）一步一步暴力跳

　　（二）倍增

当然用倍增啦~

那我们就预处理一下a[i][j]a[i][j]，记录每个节点ii往上跳2j2j步后，跳到的祖先是谁

因为ii移动2j2j次就相当于从i移动2j−12j−1次后再移动2j−12j−1次 找到状态转移方程 $father [ i ] [ j ] = father [ father [ i ] [ j -1] ] [ j-1 ] ;$

然后用dpdp做一个预处理（在bfsbfs时查到这个点就处理这个点）

ContractedBlock.gifExpandedBlockStart.gif

倍增预处理

之后就开始跳就完了

int LCA( int x,int y ){
    if( deep[x] < deep[y] ) swap( x,y ); //默认x更深 
    int h = deep[x] - deep[y];//取出高度差 
    for( int i = 0;i <= 20;i++ ) //保证每个都能测到 
        if( h & (1<<i) ) //二进制跳高度 
            x = a[x][i];
            
    if( x == y ) return y; //如果y是x的祖先，返回y就行 
    for( int i = 20;i >= 0;i-- ){ //找到第一个不相同的节点
        if( a[x][i] != a[y][i] ){
            x = a[x][i];
            y = a[y][i];
        }
    }
    return a[x][0]; //公共祖先就是第一个不相同的点的上一个点 
}

洛谷板子题

代码如下：

#include<iostream>
#include<cstdio>
#include<queue>
#define NUM 500010
using namespace std;

int n,m,s;
int fa[NUM],deep[NUM];
int a[NUM][23];
struct bian{
    int next,to;
};
bian e[NUM<<1];
int head[NUM];
bool vis[NUM];
int cnt;

void add( int x,int y ){
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
void st( int p ){
    a[p][0] = fa[p];
    for( int i = 1;i <= 20;i++ )
        a[p][i] = a[ a[p][i-1] ][i-1];
}
void bfs( int s ){
    queue <int> fat,step;
    fa[s] = s;deep[s] = 1;
    for( int i = 0;i <= 20;i++ )
        a[s][i] = s;
    fat.push(s);step.push(1);
    int nf,ns;
    vis[s] = 1;
    while( !fat.empty() ){
        nf = fat.front();
        ns = step.front();
        fat.pop();step.pop();
        for( int i = head[nf];i;i = e[i].next ){
            int to = e[i].to;
            if( vis[to] ) continue;
            fa[to] = nf;
            deep[to] = ns+1;
            vis[to] = 1;
            st(to);
            fat.push(to);step.push(deep[to]);
        }
    }
}
int LCA( int x,int y ){
    if( deep[x] < deep[y] ) swap( x,y );
    int h = deep[x] - deep[y];
    for( int i = 0;i <= 20;i++ )  
　　　　if( h & (1<<i) ) x = a[x][i];
　　 if( x == y ) return x;
    for( int i = 20;i >= 0;i-- ){
        if( a[x][i] != a[y][i] ){
            x = a[x][i];
            y = a[y][i];
        }
    }
    return a[x][0];
}

int main(){

    cin >> n >> m >> s;
    int x,y;
    for( int i = 1;i <= n-1;i++ ){
        cin >> x >> y;
        add( x,y );
        add( y,x );    
    }
    bfs( s );
//    for( int i = 1;i <= n;i++ )
        
//    for( int i = 1;i <= n;i++ ){
//        printf( "\n节点i = %d，父亲为%d,深度为%d\n",i,fa[i],deep[i] );
//        for( int j = 0;j <= 20;j++ )
//            printf( " 往上%d下，为%d\n",j,a[i][j] );
//    }
    for( int i = 1;i <= m;i++ ){
        cin >> x >> y;
        int p = LCA(x,y);
//        if( p == 0 || p == -1 ) cout << s << endl;
//        else 
        cout << p << endl;;
    }
    
    return 0;
}

Warning:加黄部分要注意，确实要这么写

如果写成如下形式则WA

int cnt = 0;
while( h&1 ){
    x = a[x][cnt];
    cnt++;
    h >>= 1;
}

因为如果hh的二进制为1101011010，则whilewhile会退出循环


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK