POJ 1330 Nearest Common Ancestors

其实看了LCA已经有好几天了就是没做题，今天找了这道题，最近树的最近公共祖先，想好好看看图论的，幸好队里买了些书，就看到这个算法的很简单就是一个深度遍历的过程。如果想更深入有了解的话推荐博客http://dongxicheng.org/structure/lca-rmq/

这种离线算法很合适很多询问的题目，这道题只有一个询问。所以我设置了一个success标志，只要找到答案就可以结束了。

代码：

[cpp]
#include<iostream>
#include<string.h>
using namespace std;
int size,a,b,ret,f[10050],head[10050];
bool visit[10050],success;
struct Edge
{
       int v,next;
} e[10050];
int Find(int x) //并查集
{
    if( x!=f[x])
        f[x]=Find(f[x]);
    return f[x];
}
void LCA(int u)
{
     visit[u]=true;
     f[u]=u;
     for(int i=head[u]; i!=-1&&!success; i=e[i].next){
          //   printf("%d %d\n",u,e[i].v);
          if( !visit[e[i].v]){
              LCA(e[i].v);
              f[e[i].v]=u;
          }
     }
     if( u==a&&visit[b]){// 因为树遍历的顺序不确定，寻找a,b和寻找b,a是一样的。
         ret=Find(b);
         success=true;
     }
     if( u==b&&visit[a]){
         ret=Find(a);
         success=true;
     }
}
int main()
{
    int t,n,i;
    scanf("%d",&t);
    while( t--){
           scanf("%d",&n);
           memset(head,-1,sizeof(head));
           memset(f,0,sizeof(f));
           memset(visit,true,sizeof(visit));
           size=0;
           for( i=1; i<n; i++){
                scanf("%d%d",&a,&b);
                visit[b]=false; //方便找到树的根节点，根节点是没有父亲结点的所以不可能作为孩子出现。
                e[size].v=b;
                e[size].next=head[a];
                head[a]=size++;
           }
           scanf("%d%d",&a,&b);
           if( a==b)
               printf("%d\n",a);
           else{
                for( i=1; i<=n; i++)//寻找根节点
                     if( visit[i])
                         break;
                success=false;
                memset(visit,false,sizeof(visit));
            //    printf("%d\n",i);
                LCA(i);
                printf("%d\n",ret);
           }
    }
    return 0;
}
作者：aacm1992

补充：软件开发 , C++ ,