2013-team4/code/lca

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
LCA 倍增算法
时间复杂度: O(NlogN)，空间复杂度: O(NlogN)
#include <iostream>
#include <cstdio>
#include <memory.h>
#define MAXN 10010

int head[MAXN],next[MAXN],link[MAXN];
int dep[MAXN],f[MAXN][16];
int n,root;
int u,v;

void dfs(int u)
{
    int now;
    now=head[u];
    while (now>0)
    {
        f[link[now]][0]=u;
        dep[link[now]]=dep[u]+1;
        dfs(link[now]);
        now=next[now];
    }
}

void build()
{
    int i,j;
    for (j=1;1<<j<=n;j++)
        for (i=1;i<=n;i++)
            if (f[i][j-1]>0)
                f[i][j]=f[f[i][j-1]][j-1];
}

int lca(int u,int v)
{
    int i, log;
    if (dep[u]<dep[v])
        i=u, u=v, v=i;
    for (log=1;1<<log<=n;log++);
    for (i=log;i>=0;i--)
        if (dep[u]-(1<<i)>=dep[v])
        {
            u=f[u][i];
            if (u==v) return u;
        }
    for (i=log;i>=0;i--)
        if (f[u][i]!=-1&&f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    return f[u][0];
}

int main()
{
    int test,i;
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d",&n);
        root=n*(n+1)/2;
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        memset(f,-1,sizeof(f));
        for (i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            next[i]=head[u];
            head[u]=i;
            link[i]=v;
            root-=v;
        }
        scanf("%d%d",&u,&v);
        dep[root]=0;
        dfs(root);
        build();
        printf("%d\n",lca(u,v));
    }
    return 0;
}
}}}

{{{
Tarjan+并查集
待补
}}}

LCA 倍增算法
时间复杂度: O(NlogN)，空间复杂度: O(NlogN)
#include <iostream>
#include <cstdio>
#include <memory.h>
#define MAXN 10010
int head[MAXN],next[MAXN],link[MAXN];
int dep[MAXN],f[MAXN][16];
int n,root;
int u,v;
void dfs(int u)
{
    int now;
    now=head[u];
    while (now>0)
    {
        f[link[now]][0]=u;
        dep[link[now]]=dep[u]+1;
        dfs(link[now]);
        now=next[now];
    }
}
void build()
{
    int i,j;
    for (j=1;1<<j<=n;j++)
        for (i=1;i<=n;i++)
            if (f[i][j-1]>0)
                f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int u,int v)
{
    int i, log;
    if (dep[u]<dep[v])
        i=u, u=v, v=i;
    for (log=1;1<<log<=n;log++);
    for (i=log;i>=0;i--)
        if (dep[u]-(1<<i)>=dep[v])
        {
            u=f[u][i];
            if (u==v) return u;
        }
    for (i=log;i>=0;i--)
        if (f[u][i]!=-1&&f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    return f[u][0];
}
int main()
{
    int test,i;
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d",&n);
        root=n*(n+1)/2;
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        memset(f,-1,sizeof(f));
        for (i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            next[i]=head[u];
            head[u]=i;
            link[i]=v;
            root-=v;
        }
        scanf("%d%d",&u,&v);
        dep[root]=0;
        dfs(root);
        build();
        printf("%d\n",lca(u,v));
    }
    return 0;
}

Tarjan+并查集
待补