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, 
0100 * 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 阅读(3518) 评论(1)  编辑 收藏 引用

评论

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

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


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