위 그래프를
로 볼 수 있다.
주어진 노드와 간선들을 모두 하나의 그래프로 보고
연결 요소가 몇 개인지 확인하는 것이다.
from collections import deque
def bfs(graph, v, visit):
que = deque([v]) # 현재 노드의 연결 요소 계산
visit[v] = True # 현재 노드 방문
while que: # 현재 노드와 연결된 노드를 전부 확인할 때까지
v = que.popleft()
for i in graph[v]: # 연결된 노드 중에서
if not visit[i]: # 연결된 노드가 방문하지 않았다면
que.append(i) # que에 다음 방문자로 지정(이 노드와 연결된 노드 확인하기 위해)
visit[i] = True # 방문
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
v1, v2 = map(int, input().split())
graph[v1].append(v2)
graph[v2].append(v1) # 연결된 노드 저장
visit = [False] * (n + 1)
cnt = 0
for v in range(1, n + 1):
if visit[v]: continue
bfs(graph, v, visit)
cnt += 1
print(cnt)