[BOJ] 9372. 상근이의 여행 (Python)

9372번: 상근이의 여행

 

* 신장 트리 (Spanning Tree)

: 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미

이때, 모든 정점을 연결하기 위한 최소 간선의 수는 n-1개입니다. (아무 그래프나 직접 그려보시면 이해하기 쉽습니다!)

 

* 최소 신장 트리 (Minimum Spanning Tree, MST)

: 신장 트리 중에 연결 비용이 가장 적은 것을 의미

 

상근이의 여행 문제는 최소 신장 트리 파트에 속해있긴 하나 비용은 고려할 필요 없는 신장 트리 문제라고 보면 됩니다.

문제 조건 상 모든 국가를 항상 방문 할 수 있는 방법이 있다는 것이고,

이때 최소 간선은 항상 국가 수 - 1 입니다!

따라서 특별한 계산 없이 바로 구할 수가 있습니다.

 

 

import sys
input = sys.stdin.readline
T = int(input()) # 테스트 케이스 수

for _ in range(T) :
    n, m = map(int, input().split()) # 국가의 수, 비행기의 종류

    for _ in range(m) :
        _, _ = map(int, input().split()) # a <-> b 왕복 비행기 
    
    print(n-1)