9372번 상근이의 여행 | Baekjoon BOJ 백준 9372 C++ 코드, 해설, 풀이

 

 

이번 포스팅은 백준 5052번 전화번호 목록입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

 

기본 알고리즘

MST 최소 신장 트리 개념 문제

MST의 원칙: 간선의 개수 = (정점의 개수)-1

 

비행 스케줄은 항상 연결 그래프

 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수 
         →모든 정점을 가장 적은 수의 간선으로 연결
          = MST (최소 신장 트리)

 

 

 

 

전체 코드

 

//백준9372 상근이의 여행
 
#include <iostream>
using namespace std;
 
int main() {
    int T;
    cin >> T;
 
    while (T--) {
        int N, M;
        cin >> N >> M;
 
        int a, b;
        while (M--) {
            cin >> a >> b;
        }
 
        cout << N - 1 << endl;
    }
 
}