[백준 9372] 상근이의 여행

www.acmicpc.net/problem/9372

9372번: 상근이의 여행

문제에서 요구하는 바만 파악하면 매우 쉬운 문제이다.

목적지를 모두 돌 수 있는 최소 비행기 수를 필요로 하므로 MST이다.

경로별 가중치가 존재하지 않고 최소 비행기 수만 요구함 + 무조건 연결그래프라는 조건이 있으므로

노드가 N개인 MST는 무조건 경로가 N-1개다.

따라서 그냥 N-1만 출력하면 된다.

#include <stdio.h>

using namespace std;
int t, n, m;
int main(void)
{
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d%d", &n, &m);
    int a, b;
    for (int i = 0; i < m; i++)
    {
      scanf("%d%d", &a, &b);
    }

    printf("%d\n", n - 1);
  }
  return 0;
}