LCA note

LCA ,最近公共祖先,是指离两个点同时为一个点(A)的子节点,而又A离这棵树的根节点最远,则A为这两个点的LCA,用图来表示则是:


在上图中 8 10的lca为 9
8 6 则为2
4 6为 1
在实际运用中,有几种做法,如下(默认查询次数为q,点数为n)

1.打暴力(不过似乎只能过样例。。。)

时间复杂度O(nq)

2.Tarjan (离线)

前置:强连通分量:如果两点间至少存在一条路径,则这两个点强连通,如果一个非强连通图有子图强连通,则该子图为强连通分量。

还是以这个图为例
要求7与4的LCA
以下是tarjan算法的过程
1.从1开始搜索,发现可以到达2,3
先去2发现可以到6,7,再去6
vis[6]=1,back[6]=2
发现6没有子节点,也没有查询,继续
查询7,以此类推查询完8,9,10;
2.查询完8,9,10返回7后,发7有要求的节点,但vis[4]=0,所以继续
当查询到4时,发现有查询请求,此时vis[4]=1,所以LCA(4,7)to LCA(find(4),find(7))to LCA(find(2),find(3))to LCA(1,1)=1
所以47的LCA为1.
下面放一道LCA裸题牛的舞会

#include<iostream>
#include<stack>
#define mmm 100000
using namespace std;
struct node {
    int v,next;
}e[50010];
stack<int> s;
int dfn[mmm],low[mmm],cnt,tot=0,ans=0,now,n,m,vis[mmm],head[mmm],jh[mmm],num[mmm];
void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void tarjan(int x)
{
    vis[x]=1;
    s.push(x);
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(vis[v]) low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x])
    {
        tot++;
        now=-1;
        while(now!=x)
        {
            now=s.top();
            s.pop();
            vis[now]=0;
            num[tot]++;
        }
    }
}
int main()
{
    int u,v;
    cin>>n>>m;
    while(m--)
    {
        cin>>u>>v;
        add(u,v);
    }
    cnt=0;
    for(int i=1;i<=n;i++)
    if(!dfn[i])
    tarjan(i);
    for(int i=1;i<=tot;i++)
    if(num[i]>1)
    ans++;
    cout<<ans;
    return 0; 
}

好了咕完了,那么

3.倍增(强制在线时使用)

还是这张图

1.前置

现在要求610的LCA,其中设dis[i]i的深度。
1.我们首先通过观察可得dis[10]-dis[6]=2,所以让点10向上走2格,使dis[6]=dis[10].
2.两个节点同时向上移动,发现第一次相遇是在2,所以LCA(6,10)=2.
但是问题来了,这种算法复杂度为O(dis[u]+dis[v]),当两点都在树的最底部并且n非常大时,仅查询一次就要O(n),超时是肯定的。因此我们需要对这个算法进行优化。

2.优化

QWQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注