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

 

Connected, Undirected인 그래프가 주어진다.

 

문제에서 중요한건, 움직이는 경로의 길이를 구하는 것이 아니라

가장 적은 종류의 비행기를 찾으라는 것이다.

 

즉,, 왔던 길을 다시 간다고 해서 길이가 추가되는 게 아니라

그냥 가장 적은 종류의 항공편을 모두 구하면 되는데

 

이는 Connected, Undirected 그래프에서 Spanning Tree를 구하라는 문제와 같다.

 

Spanning Tree는, 기존의 모든 Vertex를 포함하고, Acyclic 하고 Connected한 그래프로써

간선의 갯수는 항상 N - 1개가 된다.

 

따라서 N - 1을 출력해주면 된다.

 

// 스패닝 트리 찾기 문제
// 스패닝 트리는 connected, acyclic 이므로 항상 N - 1 개
#include <iostream>

using namespace std;

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

/*
2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5
*/