백준 알고리즘 11724번

백준링크

DFS 사용

python은 재귀제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임에러를 일으킨다.

때문에 sys.setrecursionlimit(5000) 처럼 작성

파이썬

import sys
sys.setrecursionlimit(5000)

input = sys.stdin.readline

n,m = map(int,input().split())
cnt = 0 
graph = [[] for _ in range(n+1)]


for _ in range (m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
vis = [False] * (n+1)

def dfs(v):
    vis[v] = True
    
    for i in graph[v]:
        if not vis[i]:
            dfs(i)

cnt = 0

for i in range(1,n+1):
    if not vis[i]:
        dfs(i)
        cnt+=1
    
print(cnt)