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

点击量：715

例题是洛谷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;
}