[백준 11724번] 연결 요소의 개수

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

count = 0

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

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

def dfs(graph,v,visited):

  if visited[v]:
    return False

  visited[v] = True

  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

  return True

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

print(count)

이번 문제는 전형적인 탐색 알고리즘 문제로, DFS와 BFS 중 하나를 선택해서 풀면 된다.

 

여기서 핵심은 그래프가 방향이 없는 '양방향 그래프'이기 때문에 정점들의 연결 정보를 양방향으로(graph[x].append(y), graph[y].append(x)) 연결시켜주어야 한다는 것이다 !

 

DFS의 동작원리와 구현을 연습해볼 수 있었던 간단한 문제였다 :)