[백준] 11724: 연결 요소의 개수 (Python)

문제📖

풀이🙏

• DFS를 통해 연결 요소를 찾는다.
• 이 때, visited가 False인 요소의 개수를 찾아 연결 요소의 개수를 출력한다.

코드💻

import sys
# 최대 재귀 횟수 제한을 풀어줌
sys.setrecursionlimit(10000)
v, e = map(int, input().split())
graph = [[] for i in range(v+1)]
visited = [False] * (v+1)

for i in range(e):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    graph[x].sort()
    graph[y].sort()

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

count = 0 

for i in range(1, v+1):
    if visited[i] == False:
        count += 1
        DFS(graph, i, visited)

print(count)