026.md

026 - Independent Set on a Tree (★4)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::count()

using Graph = std::vector<std::vector<int>>;

// 深さ優先探索で各頂点を 2 彩色 (色 0 or 色 1)
void DFS(const Graph& graph, int v, std::vector<int>& colors, int color01)
{
	colors[v] = color01;

	for (const auto& nv : graph[v])
	{
		if (colors[nv] != -1)
		{
			continue;
		}

		DFS(graph, nv, colors, (1 - color01));
	}
}

int main()
{
	// N 頂点の木
	int N;
	std::cin >> N;

	// N 頂点のグラフ
	Graph graph(N);
	for (int i = 0; i < (N - 1); ++i)
	{
		int a, b;
		std::cin >> a >> b;
		graph[a - 1].push_back(b - 1);
		graph[b - 1].push_back(a - 1);
	}

	// 各頂点の色, 初期値は -1
	std::vector<int> colors(N, -1);
	DFS(graph, 0, colors, 0);

	// 色 0 の頂点の個数
	const size_t numColor0 = std::count(colors.begin(), colors.end(), 0);

	// 色 1 の頂点の個数
	const size_t numColor1 = (colors.size() - numColor0);

	// 過半数の色 (色 0 or 色 1)
	const int majorColor = (numColor0 >= numColor1) ? 0 : 1;

	// 出力する頂点の残り個数
	int count = (N / 2);

	for (int i = 0; i < N; ++i)
	{
		if (colors[i] == majorColor)
		{
			std::cout << (i + 1) << ' ';

			--count;

			// N/2 個の頂点を出力したら終了
			if (count == 0)
			{
				break;
			}
		}
	}
}