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

문제: 9372번: 상근이의 여행

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

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

	int t;
	cin >> t;
	while (t-- > 0) {
		int n, m;
		cin >> n >> m;

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

		// 음.. 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수는 걍 n-1 아님..?
		// 아니 mst 문제는 최소 신장 트리에서 간선이 n-1 개 선택되어야 답인데.. 지금 이 문제는 
		// 가중치도 안 주어져 있고, 다른 조건도 없으니까 그냥 1로 놓는다고 하면
		// 그냥 n-1 의미없이 반복하는 거잖아. 
		// 그니까 그냥 답은 n-1... ;;;

		cout << n - 1 << "\n";
	}


	return 0;
}

 

음. 그냥 MST 의 성질만 알고 있으면 바로 쉽게 풀 수 있는 문제였다. 너무 쉬워서 뭐라 말할 게 없다.