木の中心

tree/tree_center.hpp · GitHub で見る

共通ページ

重みなし無向木で、ほかの頂点までの距離の最大値が最小になる頂点をすべて求めます。距離はパス上の辺数です。非空の木の中心は 1 頂点または隣接する 2 頂点で、直径の中央に一致します。頂点数の偏りを最小にする「重心」とは異なります。

#include "lib/tree/tree_center.hpp"
#include <cassert>
#include <vector>

int main() {
	std::vector<std::vector<int>> path{ {1}, {0, 2}, {1, 3}, {2} };
	assert((tree_center(path) == std::vector<int>{1, 2}));
	std::vector<std::vector<int>> star{ {1, 2, 3}, {0}, {0}, {0} };
	assert((tree_center(star) == std::vector<int>{0}));
	assert(tree_center({}).empty());
	assert((tree_center(std::vector<std::vector<int>>(1)) == std::vector<int>{0}));
}

tree_center(const std::vector<std::vector<int>>& graph) は中心の頂点番号を昇順に並べた std::vector<int> を返します。引数の既定値はありません。空の木では空列、1 頂点の木では {0}、2 頂点の木では {0,1} を返します。2 個の中心を重複して返すことはありません。返り値は入力から独立しています。

頂点数を \(n\) として、頂点番号は [0,n)、頂点数は INT_MAX 以下です。graph[v] に頂点 v の隣接頂点を並べ、各辺は両方向にそれぞれ 1 回記録してください。隣接頂点の並び順は任意です。自己辺・多重辺を持たない連結な木を渡し、非空なら無向辺数を \(n-1\) にします。森や不正なグラフ全般を検査する API ではありません。

入力を変更せず、繰り返し呼べます。重み付きの距離や辺の途中にある中心には対応しません。

葉を層ごとに取り除き、最後に残った 1 頂点または 2 頂点を返します。再帰は使いません。計算量は \(O(n)\) 時間、追加空間は \(O(n)\)、返り値の空間は \(O(1)\) です。空の木は定数時間・空間です。

コード

#ifndef TREE_CENTER_HPP
#define TREE_CENTER_HPP

#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>

[[nodiscard]] inline std::vector<int> tree_center(const std::vector<std::vector<int>> &graph) {
	assert(graph.size() <= std::size_t(std::numeric_limits<int>::max()));
	const int n = static_cast<int>(graph.size());
	if (!n) return {};
	if (n == 1) { assert(graph[0].empty()); return {0}; }
	std::vector<int> degree(n), leaves;
	leaves.reserve(n);
	[[maybe_unused]] std::size_t edges = 0;
	for (int v = 0; v < n; ++v) {
		assert(graph[v].size() < std::size_t(n));
		degree[v] = static_cast<int>(graph[v].size());
		edges += graph[v].size();
		if (degree[v] == 1) leaves.push_back(v);
	}
	assert(edges == std::size_t(n - 1) * 2);
	int remaining = n, head = 0;
	while (remaining > 2) {
		const int end = static_cast<int>(leaves.size());
		assert(head < end);
		remaining -= end - head;
		for (; head < end; ++head) for (int u : graph[leaves[head]]) {
			assert(0 <= u && u < n);
			if (--degree[u] == 1) leaves.push_back(u);
		}
	}
	assert(leaves.size() - std::size_t(head) == std::size_t(remaining));
	std::vector<int> result(leaves.begin() + head, leaves.end());
	if (result.size() == 2 && result[1] < result[0]) std::swap(result[0], result[1]);
	return result;
}

#endif

Back to top page