POJ1330Nearest Common Ancestors——近期公共祖先(离线Tarjan)

http://poj.org/problem?

id=1330

给一个有根树，一个查询节点(u,v)的近期公共祖先

836K 16MS

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

#include<string>

#include<set>

#include<map>

const int maxn=10005;

using namespace std;

int n,m;//结点数，查询数

int f[maxn];//并查集

bool vis[maxn];//訪问标记

int ancestor[maxn];//祖先

int answer[2];//存储最后的查询结果

int in[maxn];//入度

vector<int> que[maxn];

struct Edge{

    int to;

    int next;

}edge[maxn<<1];int head[maxn],tot;

void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void Init(){

    tot=0;

    memset(in,0,sizeof(in));

    memset(f,-1,sizeof(f));

    memset(head,-1,sizeof(head));

    memset(vis,false,sizeof(vis));

    memset(ancestor,0,sizeof(ancestor));

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

        que[i].clear();

    }

}

int find(int x){

    return f[x]==-1 ?

x:f[x]=find(f[x]);

}

void Union(int u,int v){

    int t1=find(u);

    int t2=find(v);

    if(t1!=t2) f[t2]=t1;

}

void LCA(int u){

    ancestor[u]=u;

    for(int i=head[u];i!=-1;i=edge[i].next){

        int v=edge[i].to;

        if(vis[v]) continue;

        LCA(v);

        Union(u,v);

        ancestor[find(v)]=u;//可省略

    }

    vis[u]=true;

    int sz=que[u].size();

    for(int i=0;i<sz;++i){

        int v=que[u][i];

        if(vis[v]){

            printf("%d\n",ancestor[find(v)]);//可替换find(v)

        }

    }

}

int main()

{

//freopen("in.txt","r",stdin);

    int T,u,v,w;

    cin>>T;

    while(T--){

        scanf("%d",&n);

        Init();

        for(int i=0;i<n-1;++i){

            scanf("%d%d",&u,&v);

            if(u!=v){

                addedge(u,v);

                in[v]++;

            }

        }

        scanf("%d%d",&u,&v);

        que[u].push_back(v);

        que[v].push_back(u);

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

            if(in[i]==0){

                LCA(i);

                break;

            }

        }

    }

    return 0;

}