백준 9372 - 상근이의 여행 (파이썬)

모든 국가가 연결되어 있기 때문에 N - 1을 출력하면 됩니다.
하지만 탐색으로 한번 풀어봤습니다.
방문하지 않은 루트로 1을 더해주면서 이동하는 쉬운 방법으로 해결했습니다.

import sys

input = sys.stdin.readline

def dfs(x, cnt):
    visited[x] = 1

    for i in graph[x]:
        if visited[i] == 0:
            cnt = dfs(i, cnt + 1)

    return cnt

for _ in range(int(input())):
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    visited = [0] * (N + 1)
    
    for __ in range(M):
        a, b = map(int, input().split())
        
        graph[a].append(b)
        graph[b].append(a)

    print(dfs(1, 0))