[백준] 9372번 상근이의 여행 파이썬 코드

코드

import sys
from collections import deque
input = sys.stdin.readline
tc = int(input())

def bfs():
  total = 0
  queue = deque([1])
  while queue:
    now = queue.popleft()
    for i in graph[now]:
      if not visited[i]:
        visited[i] = 1
        total += 1
        queue.append(i)
  return total - 1

for _ in range(tc):
  n,m = map(int, input().split())
  graph = [[] for _ in range(n+1)]
  visited = [0]*(n+1)
  for _ in range(m):
    x,y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
  res = bfs()
  print(res)

연결 그래프라서 n-1을 그냥 출력해도 된다.