Spanning-Tree

[백준_python] 상근이의 여행 || 9372 (최소 신장 트리)

www.acmicpc.net/problem/9372 9372번: 상근이의 여행첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net위 예제 입력을 보고 그래프를 따라 그려보면, 모든 정점들이 이어져 있다. 신장 트리(spanning tree)가장 적은 간선을 가진 그래프이다.n개의 정점을 가지는 그래프의 최소 간선의 개수는 n-1개이고, 이러한 트리 형태를 뜻한다. - 하나의 그래프 속에는 많은 신장 트리가 존재할 수 있다.(DFS와 BFS를 이용하여 찾을 수 있다)- 모든 정점들이 연결되어 있어야 하며,..