백준 9372 / 상근이의 여행

아.

열심히 삽질하다 계속 막혀서 해법을 찾아보니 현타가 온 문제다.

BFS 문제인척 하지만 그래프에 대한 기본을 묻는 문제.

나라가 N개이면 간선을 최소 몇 번 타야 모든 나라를 돌 수 있을까?

N-1개다.

코드

#include<stdio.h>
#include<iostream>
 
using namespace std;
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
    int testcase;
    cin >> testcase;
 
    while (testcase--) {
        
        int m, n;
        cin >> m >> n;
        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
        }
        cout << m - 1 << endl;
    }
}