문제

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

n, m = map(int, input().split())
# n : 정점의 개수, m : 간선의 개수

graph = []
for _ in range(n+1):
  graph.append([])

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

def dfs(v, visited):
  if visited[v] == False:
    visited[v] = True
    for i in graph[v]:
      dfs(i, visited)
    return True
  return False

visited = [False] * (n+1)
count = 0

for i in range(1, n+1):
  if dfs(i, visited) == True:
    count += 1

print(count)

백준 11724 연결 요소의 개수