백준 알고리즘 9372번 상근이의 여행(python)

트리 & 그래프 이론 문제이다. 문제가 웃긴게 애초에 모든 국가가 연결되있기 때문에 N-1을 출력해면 끝이다.

처음에는 이걸 생각 못해서 두 번째 코드 같ㅇ탐색해서 풀었다.

for _ in range(int(input())):
    N, M = map(int, input().split())
    for _ in range(M):
        u, v = map(int, input().split())
    print(N-1)

 

import sys

def dfs(node, cnt):
    check[node] = 1
    for n in graph[node]:
        if check[n] == 0:
            cnt = dfs(n, cnt+1)
    return cnt

for _ in range(int(sys.stdin.readline())):
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        u, v = map(int, sys.stdin.readline().split())
        graph[u].append(v)
        graph[v].append(u)
    check = [0]*(N+1)
    check[1] = 0
    cnt = dfs(1, 0)
    print(cnt)