[1일1코딩] BOJ 11724 연결 요소의 개수

 

재귀 방식으로 푼 DFS 문제

[참고]

https://letalearns.tistory.com/145

 

재귀로 푸는 만큼 재귀 제한 걸어주기!

 

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


#재귀
def dfs(idx):
    visited[idx] = 1
    for i in graph[idx]:
        if not visited[i]:
            dfs(i)

N, M = map(int, sys.stdin.readline().rstrip().rsplit())

visited = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
total = 0

for _ in range(M):
    n1, n2 = map(int, sys.stdin.readline().rstrip().rsplit())
    
    graph[n1].append(n2)
    graph[n2].append(n1)

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

print(total)