The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)

 关于LCA和RMQ问题

一、最近公共祖先(Least Common Ancestors)

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。

这里给出一个LCA的例子：

例一

对于T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}

则有：

LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3

  
二、RMQ问题(Range Minimum Query)

RMQ问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小值下标。这时一个RMQ问题的例子：

例二

对数列：5,8,1,3,6,4,9,5,7 有：

RMQ(2,4)=3
RMQ(6,9)=6

RMQ问题与LCA问题的关系紧密，可以相互转换，相应的求解算法也有异曲同工之妙。

下面给出LCA问题向RMQ问题的转化方法。

对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的深度存入数组E最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做R[i]。如果结点E[i]的深度记做D[i]，易见，这时求LCA(T,u,v)，就等价于求E[RMQ(D,R[u],R[v])]，(R[u]<R[v])。例如，对于第一节的例一，求解步骤如下：

数列E[i]为：1,2,1,3,4,3,5,3,1
R[i]为：1,2,4,5,7
D[i]为：0,1,0,1,2,1,2,1,0

于是有：

LCA(T,5,2) = E[RMQ(D,R[2],R[5])] = E[RMQ(D,2,7)] = E[3] = 1
LCA(T,3,4) = E[RMQ(D,R[3],R[4])] = E[RMQ(D,4,5)] = E[4] = 3
LCA(T,4,5) = E[RMQ(D,R[4],R[5])] = E[RMQ(D,5,7)] = E[6] = 3

易知，转化后得到的数列长度为树的结点数的两倍加一，所以转化后的RMQ问题与LCA问题的规模同次

 

数据很水，但是算法绝对经典，题目要求两个节点的最近公共祖先，这个tarjan算法使用了并查集+dfs的操作。这个算法研究了我两个小时，开始的时候在网上查找资料，写的都不尽人意，看不明白，后来干脆直接看代码，模拟了一遍，搞懂了。。。看来计算机的世界，只有代码才是王道！中间的那个并查集操作的作用，只是将已经查找过的节点捆成一个集合然后再指向一个公共的祖先。另外，如果要查询LCA(a,b)，必须把(a,b)和(b,a)都加入邻接表。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 10001
int f[MAX];
int r[MAX];
int indegree[MAX];
int visit[MAX];
vector<int> hash[MAX],Qes[MAX];
int ancestor[MAX];


void init(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {

        r[i]=1;
        f[i]=i;
        indegree[i]=0;
        visit[i]=0;
        ancestor[i]=0;
        hash[i].clear();
        Qes[i].clear();
    }

}


int find(int n)
{
    if(f[n]==n)
        return n;
    else
        f[n]=find(f[n]);
    return f[n];
}//查找函数，并压缩路径


int Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
        return 0;
    else if(r[a]<=r[b])
    {
        f[a]=b;
        r[b]+=r[a];
    }
    else
    {
        f[b]=a;
        r[a]+=r[b];
    }
    return 1;
    
}//合并函数，如果属于同一分支则返回0，成功合并返回1


void LCA(int u)
{
    ancestor[u]=u;
    int i,size = hash[u].size();
    for(i=0;i<size;i++)
    {
        LCA(hash[u][i]);
        Union(u,hash[u][i]);
        ancestor[find(u)]=u;
    }
    visit[u]=1;
    size = Qes[u].size();
    for(i=0;i<size;i++)
    {
        if(visit[Qes[u][i]]==1)
        {
            printf("%d\n",ancestor[find(Qes[u][i])]);
            return;
        }
    }
}


int main()
{

    int testcase;
    int n;
    int i,j;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
        scanf("%d",&n);
        init(n);
        int s,t;
        for(j=1;j<=n-1;j++)
        {

            scanf("%d%d",&s,&t);
            hash[s].push_back(t);
            indegree[t]++;
        }
        scanf("%d%d",&s,&t);
        Qes[s].push_back(t);
        Qes[t].push_back(s);
        for(j=1;j<=n;j++)
        {
            if(indegree[j]==0)
            {
                LCA(j);
                break;
            }
        }
    }
    return 0;
}


不过可能是用了vector的关系，耗时47MS,也许改成单纯的链表要更好些；
还有就是，如果这个树的根节点不确定，边没有方向可言的话，又应该如何做呢？（找不到根了。。。）
如果要找两个节点之间的一条通路 又该怎么办？
看来，这个问题还有继续研究下去的必要。。。

———————————————————————传说中的分割线——————————————————————————
指针版：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 10001

struct node
{

    int a;
    node *next;
}hash[MAX];
node Qes[MAX];

void Add(node hash[],int a,int b)
{

    node *p=&hash[a];
    node *q=p->next;

    node *r=new node;
    r->a=b;
    p->next=r;
    r->next=q;

}
int f[MAX];
int r[MAX];
int indegree[MAX];
int visit[MAX];
int ancestor[MAX];


void init(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {

        r[i]=1;
        f[i]=i;
        indegree[i]=0;
        visit[i]=0;
        ancestor[i]=0;
        hash[i].next=NULL;
        Qes[i].next=NULL;
    }

}


int find(int n)
{
    if(f[n]==n)
        return n;
    else
        f[n]=find(f[n]);
    return f[n];
}//查找函数，并压缩路径


int Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
        return 0;
    else if(r[a]<=r[b])
    {
        f[a]=b;
        r[b]+=r[a];
    }
    else
    {
        f[b]=a;
        r[a]+=r[b];
    }
    return 1;
    
}//合并函数，如果属于同一分支则返回0，成功合并返回1


void LCA(int u)
{
    ancestor[u]=u;
    node *p;
    for(p=hash[u].next;p!=NULL;p=p->next)
    {
        LCA(p->a);
        Union(u,p->a);
        ancestor[find(u)]=u;
    }
    visit[u]=1;
    for(p=Qes[u].next;p!=NULL;p=p->next)
    {
        if(visit[p->a]==1)
        {
            printf("%d\n",ancestor[find(p->a)]);
            return;
        }
    }
}


int main()
{

    int testcase;
    int n;
    int i,j;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
        scanf("%d",&n);
        init(n);
        int s,t;
        for(j=1;j<=n-1;j++)
        {

            scanf("%d%d",&s,&t);
            Add(hash,s,t);
            indegree[t]++;
        }
        scanf("%d%d",&s,&t);
        Add(Qes,s,t);
        Add(Qes,t,s);
        for(j=1;j<=n;j++)
        {
            if(indegree[j]==0)
            {
                LCA(j);
                break;
            }
        }
    }
    return 0;
}

汗，写了个指针版运行速度居然比vector还慢，太打击我对指针的信心了。。。可能是数据太弱了吧，指针的优势没有发挥出来。。。


——————————————————传说中的分割线——————————————————————————————————
终于用RMQ过了，起初一直RE,原来是RM Q里面的数组开小了。。。不过感觉时间效率不是很高，110MS，应该是询问的次数太少的原因吧。
RMQ应付的应该是询问次数非常巨大的情况。而且它是在线的算法，可以按顺序输出结果，这样才能AC题目啊。

 

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int>hash[10001];//用vector代替邻接表

#define MAXN   10001
#define mmin(seq, a, b)  ((seq[a] < seq[b]) ? (a) : (b))
int indegree[MAXN];
/**///// DP status
int fij[100000][100];

template <typename T>
void st(T seq[], int n)//预处理
{ 
    memset(fij, 0, 100 * MAXN * sizeof(int));
    int k = (int)(log((double)n) / log(2.0)); 
    /**/////初始状态
    for(int i = 0; i < n; i++)
        fij[i][0] = i; 
    /**/////递推计算状态
    for(int j = 1; j <= k; j++)
    {
        for(int i = 0; i + (1 << j) - 1 < n; i++)
        {
            //
            int m = i + (1 << (j - 1)); 
            //fij[i][j] = seq[fij[i][j - 1]] < seq[fij[m][j - 1]] ? fij[i][j - 1] : fij[m][j - 1];
            fij[i][j] = mmin(seq, fij[i][j - 1], fij[m][j - 1]);
        }
    }
}
template <typename T>
int RMQ(T seq[], int i, int j)//求解RMQ
{
    /**///// 用对2去对数的方法求出k
    int k = (int)(log(double(j - i + 1)) / log(2.0)); 
    /**/////
    //int t = seq[fij[i][k]] < seq[fij[j - (1 << k) + 1][k]] ? fij[i][k] : fij[j - (1 << k) + 1][k];
    int t = mmin(seq, fij[i][k], fij[j - (1 << k) + 1][k]);
    return t;
}

int E[MAXN*2+1];
int R[MAXN*2+1];
int D[MAXN*2+1];
int p=0;
void dfs(int r,int deep)//深搜，算出E,R,D数组
{
    p++;
    E[p]=r;
    D[p]=deep;
    R[r]=p;
    int i;
    int size=hash[r].size();
    for(i=0;i<size;i++)
    {

        dfs(hash[r][i],deep+1);
        p++;
        E[p]=r;
        D[p]=deep;
    }
    
}

int main()
{

    int testcase;
    int n;
    int i,j;
    int s,t;
    scanf("%d",&testcase);
    for(i=1;i<=testcase;i++)
    {
    
        scanf("%d",&n);
        for(j=1;j<=n;j++)
        {
            indegree[j]=0;
            hash[j].clear();
        }
        p=0;
            
        for(j=1;j<n;j++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            hash[a].push_back(b);
            indegree[b]++;
        }
        scanf("%d%d",&s,&t);
        int root;
        for(j=1;j<=n;j++)
        {

            if(indegree[j]==0)
            {
                root=j;
                break;
            }
        }
        dfs(root,0);
        st(D,2*n+2);
        if(R[s]<R[t])
            printf("%d\n",E[  RMQ(D,R[s],R[t]) ] );
        else
            printf("%d\n",E[ RMQ(D,R[t],R[s]) ] );

    }
    return 0;
}


 

posted on 2009-09-21 22:24 abilitytao 阅读(3535) 评论(1)  编辑 收藏 引用

评论

# re: POJ 1330 Nearest Common Ancestors(tarjan LCA 算法)[未登录] 2009-09-22 16:08 vincent

神牛平均一天切几题啊..速度很汗颜啊  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理