@zzzc18 2017-05-12T20:12:36.000000Z 字数 2071 阅读 1084

两种LCA

LCA

1. 在线：倍增
2. 离线：Tarjan

倍增

#include<cstdio>#include<cmath>#define MAXN 700000+900#define MAXM 1200000+900using namespace std;int anc[MAXN][33];int n,m,root;struct E{    int next,to;}edge[MAXM];int head[MAXN],edge_num;int depth[MAXN];int logn;void SWAP(int &x,int &y){    int t=x;x=y;y=t;}void addedge(int x,int y){    edge[++edge_num].next=head[x];    edge[edge_num].to=y;    head[x]=edge_num;}void DFS(const int &x,const int &y){    int i;    for(i=head[x];i;i=edge[i].next){        if(edge[i].to!=y){            anc[edge[i].to][0]=x;            depth[edge[i].to]=depth[x]+1;            DFS(edge[i].to,x);        }    }}void PRE(){    int i,j;    for(i=1;(1<<i)<=n;i++){        for(j=1;j<=n;j++){            if(anc[j][i-1]){                anc[j][i]=anc[anc[j][i-1]][i-1];            }        }    }}int LCA(int x,int y){    if(depth[x]<depth[y])        SWAP(x,y);    int i,j;    for(i=logn;i>=0;i--){        if(depth[y]+(1<<i)<=depth[x])            x=anc[x][i];    }    if(x==y) return x;    for(i=logn;i>=0;i--){        if(anc[x][i] && anc[x][i]!=anc[y][i]){            x=anc[x][i];y=anc[y][i];        }    }    return anc[x][0];}int main(){    scanf("%d%d%d",&n,&m,&root);    int i;int a,b;    for(i=1;i<n;i++){        scanf("%d%d",&a,&b);        addedge(a,b);addedge(b,a);    }    DFS(root,0);    PRE();    logn=floor(log(n)/log(2));    for(i=1;i<=m;i++){        scanf("%d%d",&a,&b);        printf("%d\n",LCA(a,b));    }    return 0;}

Tarjan

#include<cstdio>#include<algorithm>#define MAXN 600000using namespace std;struct E{    int next,to,id;}edge[2*MAXN],ask[2*MAXN];int head[MAXN],edge_num,h1[MAXN],a_num;int root;bool vis[MAXN];int fa[MAXN];int ans[MAXN];int n,m;void addedge(int x,int y){    edge[++edge_num].next=head[x];    edge[edge_num].to=y;    head[x]=edge_num;}void addask(int x,int y,int z){    ask[++a_num].next=h1[x];    ask[a_num].to=y;    ask[a_num].id=z;    h1[x]=a_num;}int Find(int x){    if(fa[x]!=x) fa[x]=Find(fa[x]);    return fa[x];}void LCA(int x){    int i;    vis[x]=1;    for(i=head[x];i;i=edge[i].next){        if(!vis[edge[i].to])            LCA(edge[i].to),fa[edge[i].to]=x;    }    for(i=h1[x];i;i=ask[i].next){        if(vis[ask[i].to])            ans[ask[i].id]=Find(ask[i].to);    }}int main(){    scanf("%d%d%d",&n,&m,&root);    int i;int a,b;    for(i=1;i<=n-1;i++){        scanf("%d%d",&a,&b);        addedge(a,b);        addedge(b,a);    }    for(i=1;i<=m;i++){        scanf("%d%d",&a,&b);        addask(a,b,i);addask(b,a,i);    }    for(i=1;i<=n;i++)        fa[i]=i;    LCA(root);    for(i=1;i<=m;i++)        printf("%d\n",ans[i]);    return 0;}

• 私有
• 公开
• 删除