#pragma once

#include <vector>
#include <cstdint>

namespace psemek::util
{

	template <typename Index = std::uint32_t>
	struct dsu
	{
		dsu() = default;
		dsu(Index count);

		void combine(Index x, Index y);
		Index find(Index x);

	private:
		std::vector<Index> parent_;
		std::vector<Index> size_;
	};

	template <typename Index>
	dsu<Index>::dsu(Index count)
		: parent_(count)
		, size_(count, 1)
	{
		for (Index i = 0; i < count; ++i)
			parent_[i] = i;
	}

	template <typename Index>
	void dsu<Index>::combine(Index x, Index y)
	{
		x = find(x);
		y = find(y);
		if (x != y)
		{
			if (size_[x] < size_[y])
				std::swap(x, y);
			parent_[y] = x;
			size_[x] += size_[y];
		}
	}

	template <typename Index>
	Index dsu<Index>::find(Index x)
	{
		if (parent_[x] == x)
			return x;
		return parent_[x] = find(parent_[x]);
	}

}
