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

11724 - 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

코드

from collections import deque

def bfs(n):
    q = deque()
    q.append(n)
    visited[n] = True

    while q:
        v = q.popleft()

        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True


N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

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

count = 0
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        count += 1

print(count)

한마디

무방향 그래프이기 때문에 양쪽 정점을 모두 리스트에 넣어줘야 한다.

11724번: 연결 요소의 개수