POJ 1330 Nearest Common Ancestors (LCA)

POJ 1330 Nearest Common Ancestors (LCA)

Description

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,…, N. Each of the next N -1 lines contains a pair of integers that represent an edge –the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor. Sample Input

2161 148 510 165 94 68 44 101 136 1510 116 710 216 38 116 1216 752 33 43 11 53 5

Sample Output

43

题意

树中有 ​​n​​​ 个节点， ​​n-1​​ 条边，现查询节点 a 与节点 b 的最近公共祖先。

思路

因为题中对于一棵树只有一次查询，因此我们有更简单的做法：

针对其中的一个节点，沿父路径向上标记至树根。针对另一个节点同样向上标记，直到遇到之前的标记，则此时所在的节点即为这两点最近公共祖先。

标准 LCA 离线做法：

选取树中根节点开始 dfs遍历该点 u 所有子节点 v ，并标记这些子节点 v 已被访问过若 v 还存在子节点，返回 2 ，否则下一步合并 v 节点至 u ，此时 u 、 v 属于同一集合寻找与当前点 u 有询问关系的点 v若 v 已经被访问过，则可以确认 u 和 v 的最近公共祖先为 v 被合并到的父亲节点，否则跳过

AC 代码

#include#include#includeusing namespace std;const int maxn=10001;int fa[maxn];int rank[maxn];int indegree[maxn]; //入度bool visit[maxn];vector tree[maxn],Qes[maxn];int ancestor[maxn];void init(int n){ memset(rank,0,sizeof(rank)); memset(visit,false,sizeof(visit)); memset(indegree,0,sizeof(indegree)); memset(ancestor,0,sizeof(ancestor)); for(int i=1; i<=n; i++) { fa[i]=i; tree[i].clear(); Qes[i].clear(); }}int find_set(int x) //并查集 查询+路径压缩{ if(x!=fa[x]) fa[x]=find_set(fa[x]); return fa[x];}void union_set(int x,int y) //并查集 合并{ x=find_set(x); y=find_set(y); if(rank[x]>rank[y]) fa[y]=x; else { fa[x]=y; if(rank[x]==rank[y]) rank[y]++; }}void LCA(int u){ ancestor[u]=u; int len = tree[u].size(); for(int i=0; i>cnt; while(cnt--) { cin>>n;; init(n); int s,t; for(int i=1; i>s>>t; tree[s].push_back(t); indegree[t]++; } cin>>s>>t; Qes[s].push_back(t); Qes[t].push_back(s); for(int i=1; i<=n; i++) if(!indegree[i]) { LCA(i); break; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。