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;
}
05-04 05:34