POJ Nearest Common Ancestors

点击题目打开链接

求最近公共祖先问题，不过问题只让求一组数据，用的是离线算法，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int INF=10005;
int vis[INF],fa[INF];
vector <int> edge[INF];  //存边
int e,s;
void Init(int n)  //初始化
{
    for(int i=1;i<=n;i++)
        vis[i]=0,fa[i]=-1,edge[i].clear();
}
int Find(int x)
{
    return fa[x] == -1 ? x : Find(fa[x]);
}
void Union(int u,int v)
{
    int x=Find(u);
    int y=Find(v);
    if(x!=y)
        fa[y]=x;
}
void Tarjan(int node)
{
    for(int i=0;i<edge[node].size();i++)
    {
        Tarjan(edge[node][i]);
        Union(node,edge[node][i]);
    }
    vis[node]=1;
    if(e==node && vis[s])
    {
        printf("%d\n",Find(s));
        return;
    }
    else if(s==node && vis[e])
    {
        printf("%d\n",Find(e));
        return;
    }
}
int main()
{
    int ncase;
    cin>>ncase;
    while(ncase--)
    {
        int a,b,n;
        cin>>n;
        Init(n);
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
            vis[b]=true;
        }
        scanf("%d%d",&e,&s);
        int i;
        for(i=1;i<=n;i++)
            if(vis[i]==false) break;
        memset(vis,0,sizeof(vis));
        Tarjan(i);
    }
    return 0;
}

POJ Nearest Common Ancestors,布布扣,bubuko.com

POJ Nearest Common Ancestors

原文：http://blog.csdn.net/hp_satan/article/details/22735137