[백준/BOJ/알고리즘/파이썬(Python)]#9372_상근이의 여행[트리/그래프]

 

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

9372번: 상근이의 여행

 

최소신장트리 문제를 찾아서 풀려고 했는데 다 다이아몬드 아니면 엄청 쉬운 문제 뿐....

 

위의 스케치 그림과 같이 모든 국가를 순회하려면 노란색 선분만큼 지나야 한다.

그런데 모두 연결되어 있는 그래프가 예제로 나오므로 

DFS BFS 순회를 하지 않아도 그냥 N-1(국가 수-1)만큼이 노란색 선분이다. 

 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N, M = map(int, input().split())

    for _ in range(M):
        a, b = map(int, input().split())

        #connected graph: N-1

    print(N-1)