题目连接 http://poj.org/problem?id=1330
就是构建一棵树，然后问你两个节点之间最近的公共父节点是谁？
代码：
/*Source Code
Problem: 1330 User: huifeidmeng
Memory: 1232K Time: 63MS
Language: C++ Result: Accepted Source Code
*/
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=;
vector<int> tree[maxn],qus[maxn];
int rank[maxn],father[maxn];
bool vis[maxn];
int rudu[maxn];
int lroot[maxn];
void init(int n){
memset(vis,,sizeof(vis));
memset(rudu,,sizeof(rudu));
memset(lroot,,sizeof(lroot));
for(int i=;i<=n;i++){
father[i]=i;
rank[i]=;
tree[i].clear();
qus[i].clear();
}
}
int find(int a){
while(a!=father[a])
a=father[a];
return a;
}
void Union(int a,int b)
{
int x=find(a);
int y=find(b);
if(x==y) return ;
if(rank[x]<rank[y]){
rank[y]+=rank[x];
father[x]=y;
}
else {
rank[x]+=rank[y];
father[y]=x;
}
}
void LCA(int u)
{
lroot[u]=u;
int len=tree[u].size();
for(int i=;i<len;i++){
LCA(tree[u][i]);
Union(u,tree[u][i]);
lroot[find(u)]=u;
}
vis[u]=;
int ss=qus[u].size();
for(int i=;i<ss;i++){
if(vis[qus[u][i]]){
printf("%d\n",lroot[find(qus[u][i])]);
return ;
}
}
}
int main()
{
int cas,n,u1,u2;
//freopen("test.in","r",stdin);
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
init(n);
for(int i=;i<n;i++){
scanf("%d%d",&u1,&u2);
tree[u1].push_back(u2);
rudu[u2]++;
}
scanf("%d%d",&u1,&u2);
qus[u1].push_back(u2);
qus[u2].push_back(u1);
for(int i=;i<=n;i++){
if(==rudu[i]){ //找到root
LCA(i);
break;
}
}
}
return ;
}