LCA 离线的Tarjan算法 poj1330 hdu2586

　　LCA问题有好几种做法，用到（tarjan）图拉算法的就有3种。具体可以看邝斌的博客。http://www.cnblogs.com/kuangbin/category/415390.html

　　几天的学习，我就弄懂了离线的Tarjan算法。在此，先鄙视一下哈工大出版的《图论及应用》，离线的Tarjan算法的模版用不了。害我白忙活。

　　poj1330的代码可以直接用来当模版。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int f[N], r[N], anc[N];

bool vis[N];

struct node

{

    int to,next;

}edge[N*];

int head[N],tot;

void addedge(int i, int j)

{

    edge[tot].to=j;edge[tot].next=head[i];head[i]=tot++;

    edge[tot].to=i;edge[tot].next=head[j];head[j]=tot++;

}

struct NODE

{

    int to,next,index;//index(查询编号)

}query[N*];

int h[N], res[N*], tt, q;

bool flag[N];

void add_q(int i, int j, int k)

{

    query[tt].to=j;query[tt].next=h[i];query[tt].index=k;h[i]=tt++;

    query[tt].to=i;query[tt].next=h[j];query[tt].index=k;h[j]=tt++;

}

void init(int n)

{

    for(int i=;i<=n;i++)

    {

        f[i]=-;

        r[i]=;

        vis[i]=;

        anc[i]=;

        flag[i]=;

        tot=tt=;

    }

    memset(head,-,sizeof(head));

    memset(h,-,sizeof(h));

}

int Find(int x)

{

    if(-==f[x]) return x;

    return f[x]=Find(f[x]);

}

void Link(int x,int y)

{

    int a=Find(x),b=Find(y);

    if(a!=b)

    {

        if(r[a]<=r[b]) {f[a]=b; r[b]+=r[a];}

        else  {f[b]=a; r[a]+=r[b];}

    }

}

void LCA(int u)

{

    anc[u]=u;

    vis[u]=;

    for(int k=head[u];k!=-;k=edge[k].next)

    {

        int v=edge[k].to;

        if(vis[v]) continue;

        LCA(v);

        Link(u,v);

        anc[Find(u)]=u;

    }

    for(int k=h[u];k!=-;k=query[k].next)

    {

        int v=query[k].to;

        if(vis[v])

        {

            res[query[k].index]=anc[Find(v)];

        }

    }

}

int main()

{

    //freopen("test.txt","r",stdin);

    int T,n,u,v,i;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        init(n);

        for(i=;i<n;i++)

        {

            scanf("%d%d",&u,&v);

            flag[v]=;

            addedge(u,v);

        }

        q=;

        for(i=;i<q;i++)

        {

            scanf("%d%d",&u,&v);

            add_q(u,v,i);

        }

        int root;

        for(i=;i<=n;i++)

            if(!flag[i]) {root=i; break;}

        LCA(root);

        for(i=;i<q;i++)

            printf("%d\n",res[i]);

    }

    return ;

}

　hdu2586的要求有些提高，还要求距离。假如要求u和v两点的距离，可以通过求u和v到根结点的距离,还有他们的LCA到根节点的距离。公式是dis[u] + dis[v] -2*dis[LCA[u,v]]。

//hdu2586  O(n+q)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

int f[N], r[N], anc[N];

bool vis[N];

struct node

{

    int to,next,w;

}edge[N*];

int head[N],tot;

void addedge(int i, int j,int w)

{

    edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;

    edge[tot].to=i;edge[tot].w=w;edge[tot].next=head[j];head[j]=tot++;

}

struct NODE

{

    int to,next,index;//index(查询编号)

}query[N*];

int h[N], res[N*], tt, q, dist[N];

bool flag[N];

void add_q(int i, int j, int k)

{

    query[tt].to=j;query[tt].next=h[i];query[tt].index=k;h[i]=tt++;

    query[tt].to=i;query[tt].next=h[j];query[tt].index=k;h[j]=tt++;

}

void init(int n)

{

    for(int i=;i<=n;i++)

    {

        f[i]=-;

        r[i]=;

        vis[i]=;

        anc[i]=;

        flag[i]=;

        tot=tt=;

    }

    memset(head,-,sizeof(head));

    memset(h,-,sizeof(h));

}

int Find(int x)

{

    if(-==f[x]) return x;

    return f[x]=Find(f[x]);

}

void Link(int x,int y)

{

    int a=Find(x),b=Find(y);

    if(a!=b)

    {

        if(r[a]<=r[b]) {f[a]=b; r[b]+=r[a];}

        else  {f[b]=a; r[a]+=r[b];}

    }

}

void LCA(int u)

{

    anc[u]=u;

    vis[u]=;

    for(int k=head[u];k!=-;k=edge[k].next)

    {

        int v=edge[k].to;

        if(vis[v]) continue;

        dist[v]=dist[u]+edge[k].w;

        LCA(v);

        Link(u,v);

        anc[Find(u)]=u;

    }

    for(int k=h[u];k!=-;k=query[k].next)

    {

        int v=query[k].to;

        if(vis[v])

            res[query[k].index]=anc[Find(v)];

    }

}

int a[N],b[N];

int main()

{

    //freopen("test.txt","r",stdin);

    int T,n,u,v,i,m,w;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&q);

        init(n);

        for(i=;i<n;i++)

        {

            scanf("%d%d%d",&u,&v,&w);

            flag[v]=;

            addedge(u,v,w);

        }

        for(i=;i<q;i++)

        {

            scanf("%d%d",&u,&v);

            a[i]=u;b[i]=v;

            add_q(u,v,i);

        }

        int root;

        for(i=;i<=n;i++)

            if(!flag[i]) {root=i; break;}

        dist[root]=;

        LCA(root);

        for(i=;i<q;i++)

            printf("%d\n",dist[a[i]]+dist[b[i]]-*dist[res[i]]);

    }

    return ;

}

巴特西

LCA 离线的Tarjan算法 poj1330 hdu2586

最新文章

热门文章