LCA

倍增法

在线算法

时间复杂度：

• 预处理：$O(N)$
• 查询：$O(log_2N)$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int m,n,q,anc[100][32],deep[100];
int head[100],cnt; 
struct mine
{
    int to,next;
}edge[100];
void swap(int &a,int &b){int t=a;a=b;b=t;}
void add(int x,int y)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int now,int from)
{
    for(int tmp=head[now];tmp!=0;tmp=edge[tmp].next)
    {
        if(edge[tmp].to==from) continue;//遍历无向图时防止死循环
        deep[edge[tmp].to]=deep[now]+1;
        dfs(edge[tmp].to,now);
        anc[edge[tmp].to][0]=now;
    }
}
void ready()
{
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n;j++)
            anc[j][i]=anc[anc[j][i-1]][i-1];
}
int getlca(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    int maxlogn=floor(log(n)/log(2));
    for(int i=maxlogn;i>=0;i--)
        if(deep[x]-(1<<i)>=deep[y])
                x=anc[x][i];
    if(x==y) return x;
    for(int i=maxlogn;i>=0;i--)
        if(anc[x][i]!=anc[y][i])
        {
            x=anc[x][i];y=anc[y][i];
        }
    return anc[x][0];
}
int main()
{
    freopen("lca.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
    }   
    dfs(1,1);
    ready();
    for (int i = 1; i <= n; i++) 
        for (int j = i; j <= n; j++)
            cout << i << " " << j << " " << getlca(i, j) << endl;
    return 0;
}

Tarjan法

离线算法

#include<cstdio>
using namespace std;
int n,m,root,edge_num,ask_num;
int fa[500010],head[1200000],h1[1200000],ans[500010];
bool b[500010];
struct E{
    int next,to;
}edge[1200000];
struct A{
    int next,to,num;
}ask[1200000];
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[++ask_num].next=h1[x];
    ask[ask_num].to=y;
    ask[ask_num].num=z;
    h1[x]=ask_num;
}
int Find(int x){
    if(fa[x]!=x) fa[x]=Find(fa[x]);
    return fa[x];
}
/*void Union(int a,int b){
    a=Find(a);b=Find(b);
    fa[a]=b;
}*/
void LCA(int x){
    b[x]=1;
    fa[x]=x;
    int j,u;
    for(j=head[x];j;j=edge[j].next){
        u=edge[j].to;
        if(!b[u]){
            LCA(u);
            fa[u]=x;
        }
    }
    int k;
    for(j=h1[x];j;j=ask[j].next){
        u=ask[j].to;
        k=ask[j].num;
        if(b[u]){
            ans[k]=Find(u);
        }
    }
}
void out(){
    for(int o=1;o<=m;o++){
        printf("%d\n",ans[o]);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&root);
    int i,ask1,ask2,a1,b1;
    for(i=1;i<=n-1;i++){
        scanf("%d%d",&a1,&b1);
        addedge(a1,b1);addedge(b1,a1);
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&ask1,&ask2);
        addask(ask1,ask2,i);
        addask(ask2,ask1,i);
    }
    LCA(root);
    out();
    return 0;
}

RMQ法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=500000,MAXM=100;
int a[MAXN+1],pa=0;int na[MAXN+1];
int f[MAXN+1][MAXM+1];
int head[MAXN+1],ecnt;
struct node{int to,next;} edge[MAXN+1];
void add(int x,int y)
{
    ecnt++;
    edge[ecnt].to=y;
    edge[ecnt].next=head[x];
    head[x]=ecnt;
}
void Init()
{  
    for (int i = 1; i <= pa; i++)
        f[i][0] = a[i];
    for (int k = 1; (1 << k) <= pa; k++)
        for (int i = 1; i + (1 << k) - 1 <= pa; i++)
            f[i][k] = min(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
}
int RMQ(int l, int r)
{  
    int k = 0;
    while( (1 << (k + 1)) <= r - l + 1 ) k++;
    return min( f[l][k], f[r - (1 << k) + 1][k] );
}
void dfs(int x,int d)
{
    for(int tmp=head[x];tmp;tmp=edge[tmp].next)
    {
        a[++pa]=d;na[pa]=x;
        dfs(edge[tmp].to,d+1);
    }
     a[++pa]=d;na[pa]=x;
}
int main()
{
    int u,v,N,M,S,x,y,xp,yp;
    cin>>N>>M>>S;
    for(int i=1;i<=N-1;i++)
        cin>>u>>v,add(v,u);
    dfs(S,1);
    Init();
    for(int i=1;i<=M;i++)
    {   
        cin>>x>>y;
        for(int i=1;i<=pa;i++) if(na[i]==x){xp=i;break;}
        for(int i=1;i<=pa;i++) if(na[i]==y){yp=i;break;}
        if(xp>yp) swap(xp,yp);
        cout<<na[RMQ(xp,yp)]<<endl;
    }
    return 0;
}