首页 > 代码库 > 最近公共祖先-------4.28(没整理完)

最近公共祖先-------4.28(没整理完)

最近公共祖先:在一个有根树中,结点u、v的最近公共祖先是满足是u,v的公共祖先并且深度尽可能大的结点。

1、倍增法

首先如果两个点的深度如果不同,将深度较大的点跳到与深度较小的点一样的深度,再同时向上跳,首次相遇时即为最近公共祖先。

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+15;
vector<int>vec[maxn];//记录树的边 
int n,m,x,y,p,q,t;
int dad[maxn][maxn],deep[maxn];//dad i j 为结点i的第2^j个祖先; 
int lca(int x,int y)
{
    if(deep[x]>deep[y])swap(x,y);//将深度小的结点前置 
    for(int i=20;i>=0;i--){if(deep[dad[y][i]]>=deep[x])y=dad[y][i];}//滚动到相同的深度 
    if(x==y)return x;
    for(int i=20;i>=0;i--){if(deep[dad[x][i]]!=deep[dad[y][i]]){x=dad[x][i],y=dad[y][i];}}//一起倍增找祖先 
    return dad[x][0];
}
void dfs(int x)
{
    deep[x]=deep[dad[x][0]]+1;//深度为其爸爸的深度+1 
    for(int i=0;dad[x][i];i++)
    dad[x][i+1]=dad[dad[x][i]][i];//滚动赋值,如果结点x的第2^i个祖先存在,那么x的第2^(i+1)个祖先=结点x的第2^i个祖先再往前面2^i个祖先。 
    for(int i=0;i<vec[x].size();i++)
        if(!deep[vec[x][i]]){dad[vec[x][i]][0]=x;dfs(vec[x][i]);}//记录爸爸 深搜 
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问; 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs(1);
    while(t--)
    {
        scanf("%d%d",&p,&q);
        printf("%d\n",lca(p,q));
    }
    return 0;
}

2、树剖法
size x为以x为结点的子树的结点的个数 每个结点和它的儿子之间只有一条重边,这个重边连向它的儿子中size最大的那个儿子。

如果结点u和它的儿子v之间是一条轻边,那么sizev*2<size u,因为这个儿子一定分不到它爸爸size的一半嘛。

top i 记录i结点所在链的链头,如果top u !=top v 说明u v不在一条链上 将 u=dad[u],重复上述操作;当它们在一条链上时,深度较小的那个点为他们的lca;

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+15;
vector<int>vec[maxn];
int m,n,x,y,p,q,t;
int deep[maxn],size[maxn],dad[maxn],top[maxn];
void dfs(int x)
{
    size[x]=1;deep[x]=deep[dad[x]]+1; 
    for(int i=0;i<vec[x].size();i++)
    {
        if(dad[x]!=vec[x][i])
        {
            dad[vec[x][i]]=x;
            dfs(vec[x][i]);
            size[x]+=size[vec[x][i]];//加上它儿子的size 
        }
    }
}
void dfs1(int x)
{
    int s=0;
    if(!top[x])top[x]=x;//先让每个链头赋值它本身 
    for(int i=0;i<vec[x].size();i++)
    {
        if(dad[x]!=vec[x][i]&&size[vec[x][i]]>size[s])s=vec[x][i];//寻找size最大的儿子 
    }
    if(s)//能找到size最大的儿子 
    {
     top[s]=top[x];//他的儿子结点的链头赋值上它爹 
     dfs1(s);//继续找重边 
    }
    for(int i=0;i<vec[x].size();i++)
    {
        if(dad[x]!=vec[x][i]&&vec[x][i]!=s)dfs1(vec[x][i]);//深搜它的轻边的结点里的重边 
    }
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];)//不在一个链上 
    {
    if(deep[top[x]]<deep[top[y]])swap(x,y);
    x=dad[top[x]];//将较深点赋值为他链头的爸爸; 
    }
    if(deep[x]>deep[y])swap(x,y);//深度小的结点为lca 
    return x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问; 
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    dfs(1);//赋值size deep dad 
    dfs1(1);//找重链 轻链 
    while(t--)
    {
        scanf("%d%d",&p,&q);
        printf("%d\n",lca(p,q));
    }
    return 0;
}

3、tarjian法

最近公共祖先-------4.28(没整理完)