백준 11724번: 연결 요소의 개수 (파이썬)

 

미루고 미루던 그래프 탐색 이론 2트

함수를 작성하는 것도 아직은 모르겠다.

 

일단 그래프 탐색 이론에서 꼭 들어가는거

1. 방문 기록 리스트

2. 방문 예정 리스트

 

from collections import deque

n, m = map(int, input().split())

n_dict = {i+1:[] for i in range(n)}
# 입력받은 값 저장하는 용도
for i in range(m):
  u, v = map(int, input().split())
  n_dict[u].append(v)
  n_dict[v].append(u)

# 방문했는지 안했는지의 여부 T/F
visited = [False for i in range(n+1)]

# 연결이 끊기면(?) 카운트
cnt = 0

# 정점 한 번씩 가기
for i in range(1, n+1):
  # i번이 아직 F이면
  if not visited[i]:
    # q = 방문 예정인 친구들 넣어두는 곳
    q = deque()
    q.append(i)
    # i번 방문할거니까 T
    visited[i] = True

    # 방문할 곳이 끊길때까지
    while q:
      node = q.popleft()
      for j in n_dict[node]:
        if not visited[j]:
          visited[j] = True
          q.append(j)
    cnt += 1

print(cnt)