[BOJ_C++] 9372번 : 상근이의 여행

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

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

    int t; cin >> t;
    int n, m, a, b;
    for (int tc = 0; tc < t; tc++) {
        cin >> n >> m;
        for (int i = 0; i < m; i++)
            cin >> a >> b;
        printf("%d\n", n - 1);
    }

    return 0;
}

• 최소 비용 신장 트리(MST)를 아는지에 대한 문제인 것 같다.
• 국가의 수가 있고 이후 비행 스케쥴이 주어지면 최대한 적은 종류의 비행기를 타는 것이다.
• 이때 최소 비용 신장 트리를 사용하면 모든 정점은 포함하되 최소로 연결되도록 하기 때문에 최대한 적은 비행기를 탈 수 있고, 최소 연결의 조건으로 정점의 수(국가의 수)가 n일때 간선 수는 언제나 n-1이다.
• 즉, 차례로 입력을 받은 뒤 n-1 값을 출력해주면 되는 문제이다.

결과