首页 > 代码库 > POJ 1330 Nearest Common Ancestors（Tree）
POJ 1330 Nearest Common Ancestors（Tree）
题目：Nearest Common Ancestors
根据输入建立树，然后求2个结点的最近共同祖先。
注意几点：
（1）记录每个结点的父亲，比较层级时要用；
（2）记录层级；
（3）记录每个结点的孩子，vector<int> v[M]写在主函数里面，放在外面超时。
代码：
#include<iostream>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;const int M = 10001; //vector<int> v[M];int level[M];int father[M];void visitEveryone(vector<int> v[], int one, int _level){ level[one] = _level; for(vector<int>::iterator it = v[one].begin(); it != v[one].end(); ++it) { visitEveryone(v, *it, _level+1); }}int main(){ int T,N,a,b,i,j; scanf("%d", &T); while(T--) { vector<int> v[M]; scanf("%d", &N); memset(father, 0, (N+1)*sizeof(int)); for(i = 1; i < N; ++i) { scanf("%d %d", &a, &b); father[b] = a; v[a].push_back(b); } scanf("%d %d", &a, &b); for(j=1; father[j] > 0 && j <= N; ++j); visitEveryone(v, j, 0); while(a != b) { if(level[a] < level[b]) b = father[b]; else a = father[a]; } printf("%d\n",a); } return 0;}
POJ 1330 Nearest Common Ancestors（Tree）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。