[程式] 最近共同祖先 (Lowest Common Ancestor - LCA)

LCA 算是 tree 滿容易用上的一項特性，原因在於找出任意兩點 u, v 的 LCA 後 (假設是 w)，通常問題可以拆解為：

• (u -> w) + (v -> w): 這樣的兩條路徑各自求解後合併

LCA 的找法可以參考演算法筆記中的 Jump Pointer Algorithm，他的基本概念就是對每個 node 的前 1、2、4、8 ... (2^n) 倍的祖先，如此一來，假設要知道一個 node 的前 5 代祖先是誰，只要知道他的前一代祖先的前四代祖先是誰就可以了。(簡單來說，看成用二進位表示法就知道這種儲存方式可以得知任意一個點的任意一代的祖先囉)

透過這種方法，對任意 2 點 u, v，我們可以知道最後的共同的祖先必然是 root，從上往下追蹤直到出現分歧為止，這就是最近的共同祖先拉。

實作的部分是參考這篇，原因在於 Heavy Light Decomposition 中就會用到 LCA 的概念去拆解問題。


最後的實作如下：

	/*
	* =====================================================================================
	*
	* Filename: LCA.cpp
	*
	* Description: Find the lowest common ancestor (LCA) of two nodes in a tree
	*
	* Version: 1.0
	* Created: 2018/02/24 (yyyy/mm/dd)
	* Revision: none
	* Compiler: g++ (C++ 14)
	*
	* Author: lionking
	* Organization: None
	*
	* =====================================================================================
	*/
	#include <cstdio>
	#include <cstdlib>
	#include <vector>
	#include <iterator>
	#include <algorithm>
	#include <limits>
	/**************************************************************************************
	* This class will use dynamic programming to store info for querying LCA
	* The time complexity for construction step and query will
	* require O( |V| * log |V| ) and O( log |V| ), respectively
	* where |V| is the number of vertices in a tree.
	*
	* Note:
	* 1. The given tree should be stored in adjacecy list.
	* 2. Construction step should be called prior to the query step.
	* 3. Once the given tree is modiefied, it should be re-construct before next query.
	**************************************************************************************/
	class LCA
	{
	public:
	// Construction Step:
	// it will construct necessary tables for querying LCA.
	// Return false when the construction step fails.
	//
	// Parameters:
	// 1. first/last: iterators for iterating tree nodes within [first, last)
	// 2. root: index of tree root
	//
	// Note:
	// 1. Every tree node should provide the following two iterators for iterating through its neighbors
	// a. Iterator begin(); | Iterator cbeing(); for const qualification
	// b. Iterator end(); | Iterator cend(); for const qualification
	// This is because the construction step uses range-based for to iterate neighboring nodes
	template <typename RandomAccessIterator>
	bool construct(RandomAccessIterator first, RandomAccessIterator last, size_t root);
	// Return the index of LCA(u, v)
	// The given two arguments are the indices of the tree nodes.
	// Return value is std::numeric_limits<size_t> when the query fails
	size_t query(size_t u, size_t v);
	void clear();
	private:
	std::vector< std::vector<size_t> > lca;
	std::vector<int> depth;
	// initialization step for construction
	void init(size_t root, size_t node_count);
	// DFS for tree traversal during construction
	template <typename RandomAccessIterator>
	void dfs(RandomAccessIterator first, size_t curr, size_t prev, int d = 0);
	};
	void LCA::clear()
	{
	lca.clear();
	depth.clear();
	}
	void LCA::init(size_t root, size_t node_count)
	{
	this->clear();
	// initialization steps
	this->depth.resize(node_count);
	size_t log2 = 1;
	for(; (1u << log2) <= node_count; ++log2) ;
	this->lca.resize(log2);
	for (auto& member : lca) {
	member.resize(node_count, 0);
	}
	}
	template <typename RandomAccessIterator>
	void LCA::dfs(RandomAccessIterator first, size_t curr, size_t prev, int d)
	{
	lca[0][curr] = prev;
	depth[curr] = d;
	auto& node = *(first + curr);
	for (const auto& next : node) {
	if (next != prev) {
	dfs(first, next, curr, d + 1);
	}
	}
	}
	template <typename RandomAccessIterator>
	bool LCA::construct(RandomAccessIterator first, RandomAccessIterator last, size_t root)
	{
	const size_t node_count = std::distance(first, last);
	if (node_count == 0) { return false; }
	this->init(root, node_count);
	// The previous node of tree root is root itself
	// Apply DFS to traverse the tree
	dfs(first, root, root);
	// Use DP to construct LCA table
	// lca[i][j]: the (2^i)-th ancestor of node j
	for (size_t i = 1; i < lca.size(); ++i) {
	for (size_t j = 0; j < node_count; ++j) {
	lca[i][j] = lca[i-1][ lca[i-1][j] ];
	}
	}
	return true;
	}
	size_t LCA::query(size_t u, size_t v)
	{
	if ((u >= depth.size()) || (v >= depth.size())) { return std::numeric_limits<size_t>::max(); }
	// make u be the node lower than v
	if (depth[u] < depth[v]) { std::swap(u, v); }
	// Then, find the ancestor of u, say w, such that depth[w] = depth[v].
	// This is because the lowest possible level of LCA(u, v) = depth[v]
	// Let u be w before we find the LCA(u, v) because LCA(u, v) = LCA(w, v).
	const auto diff = depth[u] - depth[v];
	for (size_t i = 0; i < lca.size(); ++i) {
	if ((diff >> i) & 1) {
	u = lca[i][u];
	}
	}
	// one possibility: v is ancestor of u; then LCA(u, v) = v.
	if (u == v) { return v; }
	// another posibility:
	for (int i = lca.size() - 1; i >= 0; --i) {
	if (lca[i][u] != lca[i][v]) {
	u = lca[i][u];
	v = lca[i][v];
	}
	}
	return lca[0][u];
	}
	int main(int argc, char *argv[])
	{
	LCA lca;
	std::vector< std::vector<size_t> > tree(11);
	tree[0].push_back(1);
	tree[0].push_back(2);
	tree[1].push_back(0);
	tree[1].push_back(3);
	tree[1].push_back(4);
	tree[2].push_back(0);
	tree[2].push_back(5);
	tree[2].push_back(6);
	tree[3].push_back(1);
	tree[3].push_back(7);
	tree[3].push_back(8);
	tree[4].push_back(1);
	tree[4].push_back(9);
	tree[4].push_back(10);
	lca.construct(tree.cbegin(), tree.cend(), 0);
	int u, v;
	while (scanf("%d %d", &u, &v) == 2) {
	if ((u < 0) || (v < 0)) { break; }
	printf("LCA(%d, %d) = %lu\n", u, v, lca.query(u, v));
	}
	return 0;
	}

view raw LCA.cpp hosted with ❤ by GitHub