백준 11724 연결요소의 개수 (Python) - DFS 활용

그래프가 주어지고
연결된 즉,몇개로 단절되어있는지 묻는 문제이다.

문제 해결방법

DFS로 시작노드에서 부터 연결된 노드를 돌면서 방문처리를 해주고,
끊긴 부분에서 카운트해주면 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n,m =map(int,input().split())
visited = [False]*(n+1)
cnt = 0
graph = [[] for i in range(n+1)] # 0부터 N까지의 빈 그래프 생성
for i in range(m):
  x,y = map(int,input().split())
  graph[x].append(y)
  graph[y].append(x)
def dfs(i):
  for k in graph[i]:
    if visited[k]:
      continue
    visited[k] = True
    dfs(k)
for i in range(1,n+1):
  if visited[i]:
     continue
  visited[i] = True
  dfs(i)
  cnt +=1
print(cnt)

DFS 개념을 완벽히 했다면 간단하게 풀릴 문제라고 생각한다.