(C++) 백준 9372번 - 상근이의 여행

문제 링크 : https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

풀이

상근이가 최소한의 수의 비행기로 모든 나라를 돌아다니는 것은 최소 신장 트리를 순회하는 것과 동일하다.

(정점 - 1) 개의 간선이 최소 신장 트리에 존재하므로, 비행기도 (정점 - 1) 개를 타게 된다.

#include <iostream>

int t, n, m, a, b;

using namespace std;

int main(){
    cin >> t;
    while(t--){
        cin >> n >> m;
        while(m--){
            cin >> a >> b;
        }
        cout << n-1 << "\n";
    }   
}