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

 

그래프에 연결 요소가 총 몇 개 있는지 카운트하는 문제다.

즉 그래프에서 모든 정점을 다 방문할 때까지 DFS나 BFS로 탐색한 횟수를 세면 된다.

DFS를 사용해서 풀었는데 RecursionError가 발생해서 인위적으로 재귀횟수를 늘리는 코드를 추가했다.

sys.setrecursionlimit(10**6)

 

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

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

for i in range(m):
    s,e = map(int,input().split())
    graph[s].append(e)
    graph[e].append(s)
    
def dfs(v):
    visited[v]=True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

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