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

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

9372번: 상근이의 여행

양방향 경로를 저장한 후 bfs로 다음 지점으로 이동할 때마다 cnt를 증가시키면서 최종 결과를 출력

from collections import deque
import sys

input = sys.stdin.readline

def bfs(x):
    q = deque()
    q.append(x)
    c[x] = 1
    cnt = 0
    while q:
        x = q.popleft()
        for nx in a[x]:
            if c[nx] == 0:
                c[nx] = 1
                cnt += 1
                q.append(nx)
    return cnt

tc = int(input())
while tc:
    n, m = map(int, input().split())
    a = [[] for _ in range(n)]
    c = [0 for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        a[x-1].append(y-1)
        a[y-1].append(x-1)
        
    ans = 0
    for i in range(n):
        if c[i] == 0:
            ans += bfs(i)
    print(ans)
    tc -= 1