[백준] 11724 | 연결 요소의 개수 [파이썬/python]

문제

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

주어진 방향 없는 그래프에서 연결 요소의 개수를 세는 문제이다.

 

접근

BFS로 그래프를 순회하며 연결 요소의 개수를 세도록 구현했다. (DFS를 사용해도 문제를 풀 수 있지만 그래프를 순회하는 데 한 가지 방법만 필요하므로 임의로 택했다.)

 

코드

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
graphs = [[] for _ in range(N+1)]
s = set(i for i in range(1, N+1))
q = deque()
ans = 0

for _ in range(M):
    u, v = map(int, input().split())
    graphs[u].append(v)
    graphs[v].append(u)
    
while s:
    q.append(s.pop())
    while q:
        for i in graphs[q.popleft()]:
            if i in s:
                q.append(i)
                s.remove(i)
    ans += 1
    
print(ans)