题目链接：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的点为树根。
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5 const int MAX_N = 10005; 6 7 int parent[MAX_N]; 8 9 void init(){ 10 for(int i=0; i<MAX_N; i++){ 11 parent[i] = i; 12 } 13 } 14 int find(int x){ 15 if(parent[x] == x) return x; 16 return parent[x] = find(parent[x]); 17 } 18 void unite(int x, int y){ 19 x = find(x); 20 y = find(y); 21 if(x == y) return ; 22 parent[y] = x; 23 } 24 bool same(int x, int y){ 25 return find(x) == find(y); 26 } 27 28 vector<int> G[MAX_N]; 29 int u, v; 30 int T; 31 int n; 32 int vis[MAX_N]; 33 int indeg[MAX_N]; 34 35 void dfs(int r){ 36 //printf("%d\n", r); 37 for(int i=0; i<G[r].size(); i++){ 38 if(!vis[G[r][i]]){ 39 dfs(G[r][i]); 40 unite(r, G[r][i]);//孩子合并到父节点 41 } 42 } 43 vis[r] = 1; //后序遍历 44 if(r == u && vis[v]){ 45 printf("%d\n", find(v)); 46 return ; 47 }else if(r == v && vis[u]){ 48 printf("%d\n", find(u)); 49 return ; 50 } 51 } 52 53 void lca(){ 54 memset(vis, 0, sizeof(vis)); 55 init(); 56 int r = 0; 57 for(int i=1; i<=n; i++){ 58 if(indeg[i]==0){ 59 //printf("root : %d\n", i); //入度为0的是树根 60 dfs(i); 61 } 62 } 63 } 64 65 int main() 66 { 67 freopen("1330.txt", "r", stdin); 68 scanf("%d", &T); 69 while(T--){ 70 scanf("%d", &n); 71 memset(indeg, 0, sizeof(indeg)); 72 for(int i=0; i<MAX_N; i++) G[i].clear(); 73 for(int i=0; i<n-1; i++){ 74 scanf("%d%d", &u, &v); 75 G[u].push_back(v);//有向图 76 indeg[v]++; 77 } 78 scanf("%d%d", &u, &v); 79 lca(); 80 } 81 return 0; 82 }
