8주차(최소신장트리) - [C++]백준9372 상근이의 여행

07 May 2022 in Study on Algorithm

백준9372 상근이의 여행 링크

문제

예제 입력

---

코드

#include<iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    for (int i = 0; i < T; i++) {
        int n, m;
        cin >> n >> m;

        int a, b;
        for (int j = 1; j <= m; j++) {
            cin >> a >> b;
        }
        cout << n-1 << "\n";
    }
}

설명

이 문제는 최소신장트리(MST)에 관련된 기본 개념 아는지 물어보는 것입니다.문제에서 간선에 가중치는 존재하지 않고 모든 노드를 방문할 수 있는 최소 방문 횟수를 원하고 있습니다. 복잡하게 생각할 것 없이 모든 곳을 방문해야하니 전제에 모든 노드를 방문할 수 있는 경로가 존재한다는 것을 생각하면 됩니다. 이런 경우에는 간선이 N-1 개인 경우가 항상 최소입니다. (MST는 항상 간선의 개수가 N-1개입니다)

---

결과