[백준] 111724번 연결 요소의 개수

 

 

이번 문제에서는 런타임 에러와 시간초과로 2번 실패했었습니다.

 

 접근법

- DFS로 접근

- 깊이 탐색 후 방문하지 않은 노드 있을 때 cnt 증가

 

에러해결

1. 런타임에러

- 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회 → 재귀 최대깊이는 재설정해줌

sys.setrecursionlimit(10000)

 

 

2. 시간초과

- input 대신 sys.stdin.readline을 통해 시간초과 해결

input = sys.stdin.readline

 

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [False]*(n+1)
cnt = 0
#dfs
def dfs(graph, a, visited):
    if not visited[a]:
       visited[a] =True
       for i in graph[a]:
           dfs(graph, i, visited)
        
for k in range(1,n+1):
    if not visited[k] :
        dfs(graph, k,visited)
        cnt +=1
    
print(cnt)