BOJ 9372번: 상근이의 여행

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

9372번: 상근이의 여행

비행기의 종류가 최소가 되어야 한다고 해서 순간 헷갈렸는데, 그냥 dfs로 그래프를 탐색하면서 모든 나라를 방문할때까지 이동하는 횟수를 카운트하면 되는 간단한 문제였다.

 

import sys
input = sys.stdin.readline
T = int(input())

def dfs(v):
    global cnt, ans
    visit[v] = True
    cnt += 1
    if (cnt==N):
        return
    for i in plane[v]:
        if (visit[i]==False):
            ans += 1
            dfs(i)
            
for _ in range(T):
    N, M = map(int, input().split())
    plane = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        plane[a].append(b)
        plane[b].append(a)
    visit = [False]*(N+1)
    cnt = 0
    ans = 0
    dfs(1)
    print(ans)