UnionFindのテンプレコード(C++)の実装

namespace data_structures {
	class union_find {
	public:
		/** @brief default constructor */
		union_find() = default;

		/**
		 * @brief constructor 
		 * @param node_count 頂点数
		 */
		union_find(int node_count) : node_count(node_count), parent(node_count, ROOT_PARENT_NUMBER), subtree_size(node_count, 1) {}

		/** @brief x番のノードが含まれる木の"根の番号"を取得 */
		int get_root_number(int x) {
			check_out_of_range_exception(x, "get_root_number");
			if (parent[x] == ROOT_PARENT_NUMBER) return x;
			else return parent[x] = get_root_number(parent[x]);
		}

		/** @brief x, y番のノード同士を併合する */
		void merge(int x, int y) {
			check_out_of_range_exception(x, "merge");
			check_out_of_range_exception(y, "merge");
			int root_of_x = get_root_number(x);
			int root_of_y = get_root_number(y);

			if (root_of_x == root_of_y) return;

			if (subtree_size[root_of_x] > subtree_size[root_of_y]) merge_operation(root_of_x, root_of_y);
			else merge_operation(root_of_y, root_of_x);
		}

		/** 
		 * @brief x, y番のノードが同じ部分木に属するか 
		 * @return true:属する false:属さない
		 */
		bool is_same_tree(int x, int y) {
			check_out_of_range_exception(x, "is_same_tree");
			check_out_of_range_exception(y, "is_same_tree");
			return get_root_number(x) == get_root_number(y);
		}

		/** @brief x番のノードが含まれる部分木のサイズを取得する */
		int get_subtree_size(int x) {
			check_out_of_range_exception(x, "get_subtree_size");
			return subtree_size[get_root_number(x)];
		}

	private:
		int node_count;
		/** @brief 根の親を表す無効な値 */
		const int ROOT_PARENT_NUMBER = -1;
		std::vector<int> parent;

		/** @brief subtree_size[i]:= iを根とした部分木のサイズ(iが根でない場合はアクセスされない) */
		std::vector<int> subtree_size;

		/**  
		 * @brief 併合操作
		 * より大きい方の根に、小さい方の部分木を併合する
		 * 部分木サイズも更新する
		 */
		void merge_operation(int bigger_root, int smaller_root) {
			parent[smaller_root] = bigger_root;
			subtree_size[bigger_root] += subtree_size[smaller_root];
		};

		/** @brief 例外チェック用のメソッド */
		void check_out_of_range_exception(int x, const std::string& method_name) const {
			if (x < 0 || node_count <= x) {
				throw std::out_of_range("data_structures::union_find::" + method_name + ": index " + std::to_string(x) + " is out of range");
			}
		}
	};
}