알고리즘 문제풀이
[백준/BOJ] 백준 9372번 : 상근이의 여행
GeniusJo
2020. 9. 23. 03:06
9372번: 상근이의 여행
첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가
www.acmicpc.net
모든 국가를 여행하기 위해 타야 되는 비행기 종류의 최소 개수는 최소 스패닝 트리의 간선의 개수이므로 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;
}