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

문제설명

---

입출력 예제

---

개념

　이 문제는 모든 국가가 연결되어 있고, 모든 비행기 티켓 가격이 동일하다는 특성 때문에 최소 신장 트리 문제처럼 보일 수 있다. 하지만 여기서 중요한 점은 상근이가 한 국가에서 다른 국가로 이동할 때, 필요에 따라 다른 국가를 거쳐갈 수 있다는 것이다. 이는 실질적으로 모든 비행기를 직접 타고 갈 필요가 없다는 것을 의미한다.

 

　따라서 이 문제의 답은 MST 알고리즘을 사용하지 않고도 간단히 구현할 수 있다. 상근이가 모든 국가를 여행하기 위해서는 전체 국가의 수 - 1 만큼의 비행기를 타면 된다. 왜냐하면 한 국가에서 출발해 모든 다른 국가를 방문하려면, 국가의 수보다 비행기를 하나 적게 타면 되기 때문이다.

---

풀이

#include<iostream>
using namespace std;

int main()
{
    int T, N, M, a, b;
    cin >> T;
    
    while(T--)
    {
        cin >> N >> M;
        
        for(int i = 0; i < M; i++)
            cin >> a >> b;
        
        cout << N-1 << "\n";
    }
}