[백준] 9372번 - 상근이의 여행

아이디어

바로 직전에 풀었던 문제 2개가 최소신장트리 문제여서 이 문제도 최소신장트리 문제인줄 알았는데, 문제를 읽어보니 가중치값이 없었다.
따라서, "상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수"는 그저 간선의 개수 - 1 이라는 것을 알 수 있었다.
다만, 이 풀이가 맞는지는 잘 모르겠다...

코드

# 상근이의 여행
import sys

T = int(sys.stdin.readline())
for _ in range(T):
    N, M = list(map(int,sys.stdin.readline().split()))
    for _ in range(M):
        a,b = list(map(int,sys.stdin.readline().split()))
    print(N-1)