[알고리즘]백준 11724 : 연결 요소의 개수 (파이썬)

11724번: 연결 요소의 개수

방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 문제이다.

연결 요소란, 노드끼리 연결되어 있는 묶음의 개수이다.

아래와 같은 경우 V1~V5, V7~V9, V10~V12가 서로 연결되어있다. 연결 요소는 총 3개이다.

접근 방법

• DFS를 수행하면 연결되어 있는 모든 노드를 탐색한다.
• 노드에 대한 방문 정보 리스트를 이용해서, visited[i] == False인 노드가 없어질 때까지 DFS를 수행하면서 수행 시마다 count를 1씩 증가시켜준다.

💡 주의사항

백준 온라인 저지의 기본 recursionlimit은 1000이다.
sys.setrecursionlimit()을 지정해주지 않으면 재귀 호출 시 런타임 에러가 발생한다.
따라서 recursionlimit을 변경해주어야 재귀 제한으로 인한 런타임 에러를 방지할 수 있다.

import sys
from collections import defaultdict

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

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)
    

visited = [False] * (n+1)

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

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

(https://www.baeldung.com/cs/graph-connected-components)