首页 > 代码库 > POJ 1330 Nearest Common Ancestors（LCA Tarjan算法）
POJ 1330 Nearest Common Ancestors（LCA Tarjan算法）
题目链接：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 int parent[MAX_N]; 7 void init(){ 8 for(int i=0; i<MAX_N; i++){ 9 parent[i] = i;10 }11 }12 int find(int x){13 if(parent[x] == x) return x;14 return parent[x] = find(parent[x]);15 }16 void unite(int x, int y){17 x = find(x);18 y = find(y);19 if(x == y) return ;20 parent[y] = x;21 }22 bool same(int x, int y){23 return find(x) == find(y);24 }25 vector<int> G[MAX_N];26 int u, v;27 int T;28 int n;29 int vis[MAX_N];30 int indeg[MAX_N];31 void dfs(int r){32 //printf("%d\n", r);33 for(int i=0; i<G[r].size(); i++){34 if(!vis[G[r][i]]){35 dfs(G[r][i]);36 unite(r, G[r][i]);//孩子合并到父节点 37 }38 }39 vis[r] = 1; //后序遍历40 if(r == u && vis[v]){41 printf("%d\n", find(v));42 return ;43 }else if(r == v && vis[u]){44 printf("%d\n", find(u));45 return ;46 }47 }48 void lca(){49 memset(vis, 0, sizeof(vis));50 init();51 int r = 0;52 for(int i=1; i<=n; i++){53 if(indeg[i]==0){54 //printf("root : %d\n", i); //入度为0的是树根 55 dfs(i);56 }57 } 58 }59 int main()60 {61 scanf("%d", &T);62 while(T--){63 scanf("%d", &n);64 memset(indeg, 0, sizeof(indeg));65 for(int i=0; i<MAX_N; i++) G[i].clear();66 for(int i=0; i<n-1; i++){67 scanf("%d%d", &u, &v);68 G[u].push_back(v);//有向图 69 indeg[v]++;70 }71 scanf("%d%d", &u, &v);72 lca();73 }74 return 0;75 }
POJ 1330 Nearest Common Ancestors（LCA Tarjan算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。