Who's Studio.

hihocCoder#1062 - 最近公共祖先·一

Word count: 438Reading time: 2 min
2016/05/15

题目

给定N对节点之间的继承关系（一个节点仅有一个父节点），给定任意两个节点，求它们的最近公共祖先节点。
具体描述请见hihoCoder。

解题思路

采用链表存储节点信息，由于存储的是子节点->父节点的关系，因此可以先遍历其中一个节点的所有祖先节点并标记，再遍历另一个节点的所有祖先节点，当遍历到一个已被标记的祖先节点时，该节点即所求结果。也可以将两个节点遍历到根节点的路径反转然后进行比较，找到开始分叉的那个节点即所求结果。

时间复杂度

时间复杂度为T（T为树的高度），最坏情况是N。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

struct Node {
	string name;
	bool visited = false;
	Node* ancestor = NULL;

	Node(string n) {
		name = n;
	}
};

string lowestComAnc(unordered_map<string, Node*> nodes, string a, string b) {
	if (a == b)
		return a;
	if (nodes.find(a) == nodes.end() || nodes.find(b) == nodes.end())
		return "-1";

	for (auto it = nodes.begin(); it != nodes.end(); it++)
		it->second->visited = false;

	Node *A = nodes[a], *B = nodes[b];
	while (A) {
		A->visited = true;
		A = A->ancestor;
	}

	while (B) {
		if (B->visited)
			return B->name;
		B = B->ancestor;
	}

	return "-1";
}

int main() {
	int N = 0, M = 0;
	cin >> N;
	unordered_map<string, Node*> nodes;
	for (int i = 0; i < N; i++) {
		string father, son;
		cin >> father >> son;
		Node* node = new Node(son);
		if (nodes.find(father) == nodes.end())
			nodes.insert(make_pair(father, new Node(father)));
		node->ancestor = nodes[father];
		nodes.insert(make_pair(son, node));
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		string a, b;
		cin >> a >> b;
		cout << lowestComAnc(nodes, a, b) << endl;
	}

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/15/2016-05-15-hihocoder-lowest-common-ancestor/

Publish date：May 15th 2016, 2:24:56 pm

Update date：December 4th 2022, 5:08:04 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目