[C++] 백준 9372번: 상근이의 여행

문제 링크

9372번: 상근이의 여행

문제 요약

N개의 국가를 모두 방문하기 위해 이용해야하는 항공편의 수를 구해야 한다. 항공편은 중복으로 사용해도 된다.

접근 방법

유니온-파인드의 연습 문제로 좀 알려져 있는데, 사실은 그래프 이론을 어느정도 이해하고 있다면 단순하게 풀 수 있습니다.

문제에서는 주어지는 그래프가 무향 연결 그래프임을 보장하고 있습니다. 조금만 더 생각하면 스패닝 트리의 형태를 떠올릴 수 있습니다. 스패닝 트리의 특성상, 그래프의 모든 정점을 포함하고 있고, 사이클은 제거됩니다. 그런데 트리에서 간선의 수는 (정점의 수) - 1이기 때문에 그냥 N - 1을 출력해 주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int t;
	cin >> t;

	while (t--)
	{
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < m; i++)
		{
			int a, b;
			cin >> a >> b;
		}
		cout << n - 1 << '\n';
	}
	return 0;
}