****

💡문제 분석 요약

방향없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하라

💡알고리즘 설계

그래프를 연결리스트로 저장한다.
그래프에 저장된 노드를 하나씩 방문한다.

2-1. 하나의 노드에 연결된 노드들을 연결 리스트로 저장하여, 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 차례로 방문한다.

2-2. dfs 함수가 더이상 호출되지 않고 끝나면 연결 요소를 모두 찾은 것이므로, 함수 호출이 끝나 연결되지 않은 다음 노드를 방문하게 되면 카운트를 하나 더하고 새 연결 요소 방문을 시작한다.

💡코드

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

N, M = map(int, input().split())
visited=[False]*(N+1)
graph= [[] for i in range(N+1)]
count=0

for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(node):
    visited[node] = True
    for a in graph[node]:
        if not visited[a]:
            dfs(a)

for i in range(1, N+1):
    if not visited[i]:
        count+=1
        dfs(i)

print(count)

💡 느낀점 or 기억할 정보

런타임 에러 (RecursionError)를 해결하기 위해 sys.setrecursionlimit(10**6) 코드를 추가한다.