Algorithm (PS)

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

minjiwoo 2023. 2. 9. 13:43
728x90

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

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

주어진 그래프는 연결그래프이다. 

모든 노드들이 연결된 상태이다. 

노드의 개수는 N개 이고, 간선의 개수는 N-1 이다. 

최소 비행기의 개수는, cycle을 형성하지 않으면서 모든 노드들을 연결해주는 간선의 개수인 N-1가 답이 된다. 

 

tree문제를 풀고 싶었는데 운좋게 얻어걸렸다 

ㅋㅋㅋㅋ

T = int(input())
for _ in range(T):
    n, m = map(int, input().split()) # node ,edge 
    for i in range(m):
        a, b = map(int, input().split())

    print(n-1)
728x90