078.md

078 - Easy Graph Problem (★2)

解答 1

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

int main()
{
	// N 頂点, M 辺
	int N, M;
	std::cin >> N >> M;

	// N 頂点のグラフ
	std::vector<std::vector<int>> graph(N);

	for (int i = 0; i < M; ++i)
	{
		int a, b;
		std::cin >> a >> b;
		graph[a - 1].push_back(b);
		graph[b - 1].push_back(a);
	}

	// 条件を満たす頂点の個数
	int count = 0;

	// 各頂点について
	for (int i = 0; i < N; ++i)
	{
		// 調べる頂点
		const auto& g = graph[i];

		// 自身の頂点番号より小さい隣接頂点の個数を調べ, もし 1 個だったら
		if (std::count_if(g.begin(), g.end(),
			[self = (i + 1)](int n){ return n < self; }) == 1) // self は自身の頂点番号
		{
			++count;
		}
	}

	// 解答を出力
	std::cout << count << '\n';
}

解答 2 (グラフを作成しない)

各頂点について、自分自身より頂点番号が小さい隣接頂点の個数を記録します。

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

int main()
{
	// N 頂点, M 辺
	int N, M;
	std::cin >> N >> M;

	// 頂点
	// 自分自身より頂点番号が小さい隣接頂点の個数を記録
	std::vector<int> v(N);

	for (int i = 0; i < M; ++i)
	{
		int a, b;
		std::cin >> a >> b;

		if (b < a)
		{
			++v[a - 1];
		}
		else if (a < b)
		{
			++v[b - 1];
		}
	}

	// 記録された個数が 1 である頂点を数える
	const auto a = std::count(v.begin(), v.end(), 1);

	// 解答を出力
	std::cout << a << '\n';
}