[Algorithm] 백준 11724 연결 요소의 개수 | 파이썬 DFS

※ 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

문제 해결 TIP

간선 정보를 이용하여 몇개의 그룹이 만들어지는지 출력하는 문제이다. 기본 DFS 알고리즘을 이용하여 풀 수 있고, 주의해야 할 점은 RecursionError가 발생하는 것이다. 1000번 이상의 recursion이 발생하면 recursion error 가 뜨기 때문에 recursionlimit을 변경해주었다.

 

전체 코드

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
#graph = [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]
#print(graph)

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

visited = [False] * (N + 1)
result = 0
for i in range(1, N + 1):
    if not visited[i]:
        dfs(graph, i, visited)
        result += 1

print(result)