[Python] 백준 11724 - 연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

문제 해결방법

bfs 로 해결 가능

노드별로 방문 결과에 대해 방문결과 값을 업데이트 하고 방문결과가 있는 노드는 skip 하고 
방문 안한 노드는 방문해서 총 몇번 반복 되는지

문제 풀이

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())
graph = dict()
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    graph.setdefault(a, { b }) if a not in graph.keys() else graph[a].add(b)
    graph.setdefault(b, { a }) if b not in graph.keys() else graph[b].add(a)


def bfs(root):
    visited = []
    queue = deque([root])

    if root not in graph.keys():
        return visited

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(list(graph[node] - set(visited)))

    return visited


count = 0
is_visited = [0] * (N + 1)

for i in range(1, N + 1):
    if is_visited[i] == 0:
        visit = bfs(i)

        for v in visit:
            is_visited[v] = 1
        count += 1
print(count)