【POJ No. 1330】 最近公共祖先 Nearest Common Ancestors

【POJ No. 1330】 最近公共祖先 Nearest Common Ancestors

北大OJ 题目地址

【题意】

一棵树如下图所示，每个节点都标有{1,2, …, 16}的整数，节点8是树根。

若节点x 位于根和y 之间的路径中，则x 是y 的祖先，节点也是自己的祖先。8、4、10和16是16的祖先，8、4、6和7是7的祖先。若x 是y 的祖先和z 的祖先，则x 被称为y和z 的公共祖先，因此8和4是16和7的公共祖先。若x 是y 和z 的公共祖先并且在它们的公共祖先中最接近y 和z ，则x 被称为y 和z 的最近公共祖先，16和7的最近公共祖先是4。若y 是z 的祖先，则y 和z 的最近公共祖先是y ，4和12的最近公共祖先是4。

编写一个程序，找到树中两个不同节点的最近公共祖先。

【输入输出】

输入：

第1行包含一个整数T ，表示测试用例的数量。每个测试用例的第1行都包含整数N （2≤N ≤10,000），表示树中的节点数。节点用1～N 标记。接下来的N -1行，每行都包含一对表示边的整数，第1个整数是第2个整数的父节点（有N 个节点的树则恰好有N -1条边）。每个测试用例的最后一行都包含两个不同的整数，求其最近公共祖先。

输出：

对每个测试用例，都单行输出两个节点的最近公共祖先。

【样例】

【思路分析】

这道题数据量不大，所以可以暴力求解最近公共祖先LCA。

【算法设计】

① 初始化父节点fa[i ]=i ，访问标记flag[i ]=0。

② 从u 向上标记到树根。

③ v 向上，第1个遇到的带有标记的节点即为u 、v 的最近公共祖先。

【算法实现】

#include

using namespace std;

const int maxn=10010;
int fa[maxn];
bool flag[maxn];

void Init(int n){
	for(int i=1;i<=n;i++){
		fa[i]=i;
		flag[i]=0;
	} 
}

int LCA(int u,int v){
    if(u==v)
    	return u;
	flag[u]=1;
	while(fa[u]!=u){//u向上走到根
		u=fa[u];
		flag[u]=1;
	}
	if(flag[v]) 
		return v;
	while(fa[v]!=v){//v向上
		v=fa[v];
		if(flag[v])
			return v;
	}
	return 0;   	
}

int main(){
	int n,u,v,T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		Init(n);
		for(int i=1;i<n;i++){
			scanf("%d%d",&u,&v);
			fa[v]=u;
		}
		scanf("%d%d",&u,&v);
		printf("%d\n",LCA(u,v));
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49