最近共通祖先 (LCA)
(GraphTheory/LowestCommonAncestor.hpp)

View this file on GitHub
Last update: 2022-05-15 21:01:40+09:00
Include: #include "GraphTheory/LowestCommonAncestor.hpp"
Link: https://tkmst201.github.io/Library/GraphTheory/LowestCommonAncestor.hpp

概要

頂点数 $N$ の木で任意の $2$ 頂点の最近共通祖先を事前計算 $\Theta(N \log{N})$ クエリ $\Theta(\log{N})$ で求めることのできるライブラリです。
実は重軽分解 ( HL 分解) を用いた LCA の方が高速かつ使用メモリも少ないです(事前計算 $\Theta(N\log{\log{N}})$ クエリ $\Theta(\log{\log{N}})$ )、森にも対応しています。

LowestCommonAncestor(const Graph & g, int root = 0)
- 時間/空間 $\Theta(N \log{N})$ 根 root の根付き木 $g$ (頂点数 $N$) で初期化
int size()
- $\Theta(1)$ グラフの頂点数 $N$ を返す
int find(int a, int b)
- $\Theta(\log{N})$ 頂点 $a$, $b$ の最近共通祖先を返す
int parent(int u, int k = 1)
- $\Theta(\log{N})$ 頂点 $u$ の $k$ 回根方向に辺をたどった頂点を返す
int depth(int u)
- $\Theta(1)$ 頂点 $u$ から根までのパス上にある辺の個数を返す

コンストラクタ

LowestCommonAncestor(const Graph & g, int root = 0)

根 root の根付き木 $g$ (頂点数 $N$ ) で初期化します。

制約

$0 \leq$ root $< N$
g は根付き木または木

計算量

時間/空間 $\Theta(N \log{N})$

メンバ関数

以下、グラフの頂点数を $N$ とします。

int size()

グラフの頂点数 $N$ を返します。

計算量

$\Theta(1)$

int find(int a, int b)

頂点 $a$, $b$ の最近共通祖先を返します。

制約

$0 \leq a, b < N$

計算量

$\Theta(\log{N})$

int parent(int u, int k = 1)

頂点 $u$ の $k$ 回根方向に辺をたどった頂点を返します。

制約

$0 \leq u < N$
$0 \le N$
頂点 $u$ から根までのパス上にある辺の個数は $k$ 個以下

計算量

$\Theta(\log{N})$

int depth(int u)

頂点 $u$ から根までのパス上にある辺の個数を返します。

制約

$0 \leq u < N$

計算量

$\Theta(1)$

使用例

#include <bits/stdc++.h>
#include "GraphTheory/LowestCommonAncestor.hpp"
using namespace std;

int main() {
	LowestCommonAncestor::Graph g(6);
	//         1
	//    2        3
	// 0    4          5
	g[1].emplace_back(2);
	g[1].emplace_back(3);
	g[2].emplace_back(0);
	g[2].emplace_back(4);
	g[3].emplace_back(5);
	
	g[5].emplace_back(3); // 逆辺があっても良い
	
	LowestCommonAncestor lca(g, 1);
	
	cout << "size() = " << lca.size() << endl; // 6
	
	cout << "find(2, 3) = " << lca.find(2, 3) << endl; // 1
	cout << "find(2, 5) = " << lca.find(2, 5) << endl; // 1
	cout << "find(1, 3) = " << lca.find(1, 3) << endl; // 1
	cout << "find(0, 4) = " << lca.find(0, 4) << endl; // 2
	cout << "find(0, 2) = " << lca.find(0, 2) << endl; // 2
	cout << "find(0, 0) = " << lca.find(0, 0) << endl; // 0
	cout << "find(0, 5) = " << lca.find(0, 5) << endl; // 1
	
	cout << "parent(4) = " << lca.parent(4) << endl; // 2
	cout << "parent(4, 2) = " << lca.parent(4, 2) << endl; // 1
	cout << "parent(3, 0) = " << lca.parent(3, 0) << endl; // 3
	
	cout << "depth(1) = " << lca.depth(1) << endl; // 0
	cout << "depth(2) = " << lca.depth(2) << endl; // 1
	cout << "depth(0) = " << lca.depth(0) << endl; // 2
	cout << "depth(5) = " << lca.depth(5) << endl; // 2
}

Verified with

Code

#ifndef INCLUDE_GUARD_LOWEST_COMMON_ANCESTOR_HPP
#define INCLUDE_GUARD_LOWEST_COMMON_ANCESTOR_HPP

#include <vector>
#include <cassert>
#include <utility>
#include <cstdint>
#include <stack>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/LowestCommonAncestor.hpp
 */
struct LowestCommonAncestor {
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n, logn;
	std::vector<std::vector<int>> par;
	std::vector<int> depth_;
	
public:
	LowestCommonAncestor(const Graph & g, int root = 0) : n(g.size()) {
		assert(0 <= root && root < n);
		logn = 1;
		while ((1 << logn) + 1 <= n) ++logn;
		par.assign(logn, std::vector<int>(n, -1));
		depth_.assign(n, 0);
		std::stack<std::pair<int, int>> stk;
		par[0][root] = root;
		stk.emplace(root, root);
		while (!stk.empty()) {
			const auto [u, p] = stk.top();
			stk.pop();
			for (int v : g[u]) {
				if (v == p) continue;
				assert(0 <= v && v < n);
				par[0][v] = u;
				depth_[v] = depth_[u] + 1;
				stk.emplace(v, u);
			}
		}
		for (int i = 1; i < logn; ++i) {
			for (int j = 0; j < n; ++j) par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	
	int size() const noexcept {
		return n;
	}
	
	int find(int a, int b) const noexcept {
		assert(0 <= a && a < size());
		assert(0 <= b && b < size());
		assert(par[0][a] != -1);
		assert(par[0][b] != -1);
		if (depth_[a] < depth_[b]) std::swap(a, b);
		a = parent(a, depth_[a] - depth_[b]);
		if (a == b) return a;
		for (int i = logn - 1; i >= 0; --i) {
			if (par[i][a] != par[i][b]) a = par[i][a], b = par[i][b]; 
		}
		return par[0][a];
	}
	
	int parent(int u, int k = 1) const noexcept {
		assert(0 <= u && u < size());
		assert(0 <= k && k <= depth_[u]);
		assert(par[0][u] != -1);
		for (int i = 0; i < logn; ++i) if (k >> i & 1) u = par[i][u];
		return u;
	}
	
	int depth(int u) const noexcept {
		assert(0 <= u && u < size());
		assert(par[0][u] != -1);
		return depth_[u];
	}
};

#endif // INCLUDE_GUARD_LOWEST_COMMON_ANCESTOR_HPP

#line 1 "GraphTheory/LowestCommonAncestor.hpp"



#include <vector>
#include <cassert>
#include <utility>
#include <cstdint>
#include <stack>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/LowestCommonAncestor.hpp
 */
struct LowestCommonAncestor {
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n, logn;
	std::vector<std::vector<int>> par;
	std::vector<int> depth_;
	
public:
	LowestCommonAncestor(const Graph & g, int root = 0) : n(g.size()) {
		assert(0 <= root && root < n);
		logn = 1;
		while ((1 << logn) + 1 <= n) ++logn;
		par.assign(logn, std::vector<int>(n, -1));
		depth_.assign(n, 0);
		std::stack<std::pair<int, int>> stk;
		par[0][root] = root;
		stk.emplace(root, root);
		while (!stk.empty()) {
			const auto [u, p] = stk.top();
			stk.pop();
			for (int v : g[u]) {
				if (v == p) continue;
				assert(0 <= v && v < n);
				par[0][v] = u;
				depth_[v] = depth_[u] + 1;
				stk.emplace(v, u);
			}
		}
		for (int i = 1; i < logn; ++i) {
			for (int j = 0; j < n; ++j) par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	
	int size() const noexcept {
		return n;
	}
	
	int find(int a, int b) const noexcept {
		assert(0 <= a && a < size());
		assert(0 <= b && b < size());
		assert(par[0][a] != -1);
		assert(par[0][b] != -1);
		if (depth_[a] < depth_[b]) std::swap(a, b);
		a = parent(a, depth_[a] - depth_[b]);
		if (a == b) return a;
		for (int i = logn - 1; i >= 0; --i) {
			if (par[i][a] != par[i][b]) a = par[i][a], b = par[i][b]; 
		}
		return par[0][a];
	}
	
	int parent(int u, int k = 1) const noexcept {
		assert(0 <= u && u < size());
		assert(0 <= k && k <= depth_[u]);
		assert(par[0][u] != -1);
		for (int i = 0; i < logn; ++i) if (k >> i & 1) u = par[i][u];
		return u;
	}
	
	int depth(int u) const noexcept {
		assert(0 <= u && u < size());
		assert(par[0][u] != -1);
		return depth_[u];
	}
};

最近共通祖先 (LCA) (GraphTheory/LowestCommonAncestor.hpp)

概要

コンストラクタ

LowestCommonAncestor(const Graph & g, int root = 0)

メンバ関数

int size()

int find(int a, int b)

int parent(int u, int k = 1)

int depth(int u)

使用例

Verified with

Code

最近共通祖先 (LCA)
(GraphTheory/LowestCommonAncestor.hpp)