tarjan学习笔记1 最近公共祖先 LCA【tarjan】

作者: wjyyy 分类: LCA,tarjan,学习笔记 发布时间: 2018-06-06 15:39

点击量:64

例题是洛谷P3379

 

   最近公共祖先可以用倍增做,也可以用tarjan做,不过tarjan是离线的,理论上效率要高一些。

 

   今天学习的是用tarjan算法求LCA。 需要用到的数据结构:并查集。首先给每个节点的并查集初始化s[i]=i。我们从一棵树的根节点开始做dfs,每遍历到一个点就将vis数组置1,说明这个点已经被处理过了,目前不改变这个点的集合,s[x]=x,并把后面的点的from改成x,然后继续dfs。

 

   直到叶子节点,我们开始回溯,在回溯过程中,在dfs(x)结束之前,将x的集合s[x]归为from[x]的集合。原因:在以x为根节点的子树中,相互的询问已经处理完毕,后面要遍历的点与x子树中的点的最近公共祖先最深也只有可能是x的父亲。那么我们可以看出,更新后,s[x]中存的是x节点的父亲(而它的孩子的s[]不一定是父亲,并查集可以路径压缩),因为在这个公共祖先回溯前,这个节点的祖先就是它自己,体现了最近的思想,这也就是tarjan算法的正确性。

 

   我们在dfs过程中,可能会遇到一些查询,如果遍历到x时查询lca(x,y),当y没有被遍历过时,就不管这个询问,如果y被遍历过(vis[y]==true),就直接返回my_find(y)。

 

#include<cstdio>
#include<cstring>
struct node
{
    int n,cnt;
    node *nxt;
    node(int n,int cnt)
    {
        this->n=n;
        this->cnt=cnt;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[500012],*tail[500012];
node askh[500012],*askt[500012];
int s[500012];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
bool vis[500012];
int ans[500012];
bool used[500012];
bool Used[500012];
void dfs(int x,int from)
{
    vis[x]=true;
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(Used[p->n])
            continue;
        Used[p->n]=true;
        dfs(p->n,x);
        Used[p->n]=false;
    }
    p=&askh[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(vis[p->n]&&!used[p->cnt])
        {
            ans[p->cnt]=my_find(p->n);
            used[p->cnt]=true;
        }
    }
    s[x]=from;
    return;
}
int main()
{
    memset(Used,0,sizeof(Used));
    memset(used,0,sizeof(used));
    memset(vis,0,sizeof(vis));
    int n,m,S,u,v;
    scanf("%d%d%d",&n,&m,&S);
    for(int i=1;i<=n;i++)
    {
        s[i]=i;
        tail[i]=&head[i];
        askt[i]=&askh[i];
    }

    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        tail[u]->nxt=new node(v,0);
        tail[u]=tail[u]->nxt;
        tail[v]->nxt=new node(u,0);
        tail[v]=tail[v]->nxt;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        askt[u]->nxt=new node(v,i);
        askt[u]=askt[u]->nxt;
        askt[v]->nxt=new node(u,i);
        askt[v]=askt[v]->nxt;
    }
    Used[S]=true;
    dfs(S,S);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */