[백준] 9372 파이썬(python)

문제

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

 

문제 풀이

import collections
import sys

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


def bfs(graph, i, visited, count):
    # visited[i] = 1
    queue = collections.deque([i])

    while queue:
        node = queue.popleft()

        if visited[node] == 0:
            visited[node] = 1
            count += 1
            queue.extend(graph[node])

    return count


for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N + 1)]
    visited = [0] * (N + 1)
    count = 0

    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(1, len(graph)):
        if visited[i] == 0:
            count = bfs(graph, i, visited, count)

    print(count - 1)