[BOJ] 9372: 상근이의 여행

문제 소개

2020.03.30 기준,  solved.ac 실버 3티어 문제입니다.

 

솔직히 최근에 푼 문제 중에 제일 어이가 없었던 문제입니다.

주의, 이 문제는 아이디어를 보면 스포가 됩니다.

 

문제 링크

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

아이디어

이 문제는 정말 친절하게도 주어지는 그래프가 연결 그래프라고 합니다.

연결 그래프를 몇 개 그려보면서 MST(최소 신장 트리)의 가중치 합을 한번 구해보시면, 무조건 (노드의 개수 - 1)이라는 것을 알게 됩니다. 

따라서, 그냥 주어지는 n 을 입력받고 (n-1)을 출력하면 끝납니다.

 

 

코드

T = int(input())
for i in range(T):
    n,m=map(int,input().split())
    for i in range(m):
        input()
    print(n-1)

Rmx