[백준/BOJ] 백준 9372번 : 상근이의 여행

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

모든 국가를 여행하기 위해 타야 되는 비행기 종류의 최소 개수는 최소 스패닝 트리의 간선의 개수이므로 n-1이다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int tc;
	int n, m;
	int a, b;

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		cin >> n >> m;

		for (int i = 0; i < m; i++)
		{
			cin >> a >> b;
		}

		//모든 국가를 여행하기 위해 타야되는 비행기 종류의 최소 개수는 최소스패닝 트리의 간선의 개수이므로 n-1이다
		cout << n - 1 << "\n";
	}

	return 0;
}