[Python | 백준] 11724번: 연결 요소의 개수

방향 없는 그래프 주어짐 -> 연결 요소(connected component) 개수 구하는 프로그램

 

아이디어

그래프 탐색 (DFS/BFS)

방문 못한 노드 하나라도 있다면 카운트 증가하고

그 방문 못한 노드 (false 노드)에서 시작해서 다시 그래프 탐색

false 노드 없을 때까지 그래프 탐색 반복

 

풀이 - DFS 사용

import sys
input = sys.stdin.readline

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)

def dfs(v):
    stack = [v]
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.append(neighbor)

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

 

DFS 재귀 사용하니 또 Recursion Error 나서 stack으로 바꿔주고, 

시간 초과가 나서 sys 사용하여 입력 받도록 바꿔주었다.