poj 1330 Nearest Common Ancestors 夜

http://poj.org/problem?id=1330

最近公共父结点

离线算法  LCA

用并查集 和 dfs

每搜到一个点 先让其父结点等于自己

继续往下搜 这时如果询问已搜过的点 则两点之间的最近公共父结点就是 已搜过的点的最上父结点

若没搜过 就继续深搜

所用相连的点都搜完后 让此点的父结点为上一层结点

#include<iostream>
#include<cstring>

using namespace std;

const int N=10005;
struct node
{
    struct tt *next;
}mem[N];
struct tt
{
    struct tt *next;
    int j;
};
void build(int i,int j)
{
    struct tt *t=new tt;
    t->j=j;
    t->next=mem[i].next;
    mem[i].next=t;
}
bool had[N];
bool visited[N];
int f[N];
int l,r;
int ans;
int findf(int x)
{
    if(x!=f[x])
    f[x]=findf(f[x]);
    return f[x];
}
void searchans(int x)
{
    if(x==l)
    {
        if(visited[r]==true)
        {
            ans=findf(r);
        }
    }
    else
    {
        if(visited[l]==true)
        {
            ans=findf(l);
        }
    }
    //cout<<x<<" "<<ans<<endl;
}
void dfs(int pre,int x)
{

    visited[x]=true;
    f[x]=x;
    if(x==l||x==r)
    searchans(x);
    struct tt *t=mem[x].next;
    while(t!=NULL)
    {
        if(visited[t->j]==false)
        dfs(x,t->j);
        t=t->next;
    }
    f[x]=pre;
}
void Lca(int n)
{
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;++i)
    {
        if(had[i]==false)
        {
            dfs(i,i);
            break;
        }
    }
}
void Clear(int n)
{
    for(int i=1;i<=n;++i)
    mem[i].next=NULL;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        memset(had,false,sizeof(had));
        for(int w=1;w<n;++w)
        {
            int i,j;
            cin>>i>>j;
            had[j]=true;
            build(i,j);
        }
        cin>>l>>r;
        Lca(n);
        cout<<ans<<endl;
        Clear(n);
    }

    return 0;
}