Loading...

LCA(最近公共祖先)

check评论:0 条 remove_red_eye浏览量:406 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-12

终于搞懂了LCA……
1.倍增
思路理一下:

  • 首先处理深度,把每个点的深度先找出来
  • 寻找两个点的最近公共祖先,先让他们爬到同一深度
  • 如果相同就返回
  • 否则两个同时向上爬,最后返回当前点
    code:
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500010
int f[MAXN][22],d[MAXN];
struct edge
{
    int next,to;
}e[MAXN<<1];
int ei=0;
int head[MAXN];
void add(int a,int b)
{
    e[ei].to=b;
    e[ei].next=head[a];
    head[a]=ei++;
} 
void dfs(int u,int r)
{
    d[u]=d[r]+1;
    f[u][0]=r;
    for(int i=1;(1<<i)<=d[u];i++)
    {
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=r)
        {
            dfs(v,u);
        }
    }
}
int lca(int a,int b)
{
    if(d[a]>d[b])
    {
        swap(a,b);
    }
    for(int i=20;i>=0;i--)
    {
        if(d[a]<=d[b]-(1<<i))
        {
            b=f[b][i];
        }
    }
    if(a==b)
    {
        return a;
    }
    for(int i=20;i>=0;i--)
    {
        if(f[a][i]==f[b][i])
        {
            continue;
        }
        b=f[b][i];
        a=f[a][i];
    }
    return f[a][0];
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(s,0);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
}

2.tarjan
tarjan有个比较大的问题,就是它是离线的
但是还比较好写啊qwq
步骤:

  • 先建立两个链表,一个为树的各条边,另一个是需要查询最近公共祖先的两节点
  • 建好后,从根节点开始进行一遍深搜
  • 先把该节点u的father设为他自己(也就是只看大树的一部分,把那一部分看作是一棵树),搜索与此节点相连的所有点v,如果点v没被搜索过,则进入点v的深搜,深搜完后把点v的father设为点u
  • 深搜完一点u后,开始判断节点u与另一节点v是否满足求LCA的条件,满足则将结果存入数组中
  • 搜索完所有点,自动退出初始的第一个深搜,输出结果
    code:
#include <bits/stdc++.h>
using namespace std;
int n,m,s,fa[2000001],ans[2000001];
int head[2000001],head2[2000001];
int vis[2000001];
struct edge
{
    int next,to;
}e1[2000001];
struct edge1
{
    int next,to,num;
}e2[2000001];
int ei=0;
int add(int x,int y)
{
    ei++;
    e1[ei].to=y;
    e1[ei].next=head[x];
    head[x]=ei;
}
int add1(int x,int y,int i)
{
    ei++;
    e2[ei].to=y;
    e2[ei].num=i;
    e2[ei].next=head2[x];
    head2[x]=ei;
}
int find(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=find(fa[x]);
}
int uion(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        fa[x]=y;        
    }
}
int tarjan(int f)
{
    fa[f]=f;
    vis[f]=1;
    for(int i=head[f];i>0;i=e1[i].next)
    {
        int t=e1[i].to;
        if(vis[t]==1) 
        {
            continue;
        }
        tarjan(t);
        uion(t,f);
    }
    for(int i=head2[f];i;i=e2[i].next)
    {
        int t=e2[i].to;
        if(vis[t]==0)
        {
            continue;
        }
        ans[e2[i].num]=find(t);
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    ei=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);    
        add1(x,y,i);
        add1(y,x,i);
    }
    tarjan(s);
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",ans[i]);
    }
}

3.树链剖分
步骤如下:

  • 首先,找出所有点的top,fa(见树链剖分)
  • 然后只要两个点top不一样(不在同一条重链上,就把top深度的那个点爬到它top的fa上去)
  • 当top一样时,输出比较浅的点即可
    code:
#include <stdio.h>
#include <iostream>
using namespace std;
#define maxn 100005
int top[maxn],fa[maxn],son[maxn],siz[maxn],head[maxn],dep[maxn];
struct edge
{
    int next,to;
}e[maxn<<1];
int tot=0;
void add(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
void dfs1(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        dep[v]=dep[u]+1;
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        } 
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    tot++;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        dfs2(v,v);
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
        {
            swap(u,v);
        }
        u=fa[top[u]];
    } 
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    return u;
}
int main()
{
    int n,q,s;
    cin>>n>>q>>s;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dep[s]=1;
    tot=0;
    dfs1(s);
    tot=0;
    dfs2(s,s);
    for(int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名