[Python] 연결 요소의 개수 - 백준 (DFS)

해당 글은 백준 11724번 '연결 요소의 개수' 문제를 다룬다.

문제

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

11724번: 연결 요소의 개수

 

설명

해당 문제는 DFS로 방문여부를 확인하며 모두 탐색해보면 되는 간단한 문제이다.

여기서 주의할 점은 재귀한계를 늘려주고, input을 sys.stdin.readline으로 설정하여 시간을 줄이지 않으면 시간초과가 뜬다.

 

코드

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

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

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

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