백준 11724

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

dfs를 떠올렸고, 노드를 순차적으로 탐색하면서 만약 해당 노드가 방문되지 않았다면 해당 노드를 방문 처리하고, dfs를 통해 해당 노드와 연결된 노드 중 방문 처리되지 않은 노드를 방문 처리한다. 이렇게 탐색을 마치고 나면 이것이 하나의 연결 요소가 되므로 cnt += 1을 해준다. 이 과정을 모든 노드에 대해 반복하면 된다.

코드(정답, PyPy3)는 다음과 같다.

# 11724

import sys

n, m = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

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

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

print(cnt)

Python3 환경에서 돌리면 런타임 에러가 뜬다. 이는 Python3, PyPy의 구현이 다르기 때문이라고 한다..

참고

https://jobdong7757.tistory.com/57