题目链接：http://poj.org/problem?id=1330
题意：给定一个n个节点的有根树，以及树中的两个节点u,v，求u,v的最近公共祖先。
数据范围：n [2, 10000]
思路：从树根出发进行后序深度优先遍历，设置vis数组实时记录是否已被访问。
每遍历完一棵子树r，把它并入以r的父节点p为代表元的集合。这时判断p是不是所要求的u, v节点之一，如果r==u，且v已访问过，则lca(u, v)必为v所属集合的代表元。p==v的情况类似。
我的第一道LCA问题的Tarjan算法，题目只有唯一的一组查询，实现起来非常简洁。
注意题目给树的格式：给出n-1个数对<u, v>，u为v的父节点。因此可以当作有向图用邻接表存储，同时记录各个节点的入度，入度为0的点为树根。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = ; int parent[MAX_N]; void init(){
for(int i=; i<MAX_N; i++){
parent[i] = i;
}
}
int find(int x){
if(parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unite(int x, int y){
x = find(x);
y = find(y);
if(x == y) return ;
parent[y] = x;
}
bool same(int x, int y){
return find(x) == find(y);
} vector<int> G[MAX_N];
int u, v;
int T;
int n;
int vis[MAX_N];
int indeg[MAX_N]; void dfs(int r){
//printf("%d\n", r);
for(int i=; i<G[r].size(); i++){
if(!vis[G[r][i]]){
dfs(G[r][i]);
unite(r, G[r][i]);//孩子合并到父节点
}
}
vis[r] = ; //后序遍历
if(r == u && vis[v]){
printf("%d\n", find(v));
return ;
}else if(r == v && vis[u]){
printf("%d\n", find(u));
return ;
}
} void lca(){
memset(vis, , sizeof(vis));
init();
int r = ;
for(int i=; i<=n; i++){
if(indeg[i]==){
//printf("root : %d\n", i); //入度为0的是树根
dfs(i);
}
}
} int main()
{
freopen("1330.txt", "r", stdin);
scanf("%d", &T);
while(T--){
scanf("%d", &n);
memset(indeg, , sizeof(indeg));
for(int i=; i<MAX_N; i++) G[i].clear();
for(int i=; i<n-; i++){
scanf("%d%d", &u, &v);
G[u].push_back(v);//有向图
indeg[v]++;
}
scanf("%d%d", &u, &v);
lca();
}
return ;
}