[WEEK03] 19일차. 그래프 탐색

11724 연결 요소의 개수

연결 요소란?

위 그림에서 연결 요소는 2개다.

연결 요소는 다음과 같은 조건을 가진다.

• 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
• 다른 연결 요소와 연결되는 경로가 있으면 안된다.

코드는 다음과 같다.

BFS

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())

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


def bfs(start):
    Q = deque([start])
    visited[start] = 1
    while Q:
        current = Q.popleft()
        for nx in graph[current]:
            if not visited[nx]:
                Q.append(nx)
                visited[nx] = 1
cnt = 0
for i in range(1, N + 1):
    if not visited[i]:
        bfs(i)
        cnt += 1

print(cnt)

DFS

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

N, M = map(int, input().split())

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

def dfs(k):
    visited[k] = 1
    for nx in graph[k]:
        if not visited[nx]:
            dfs(nx)

cnt = 0

for i in range(1, N+1):
    if not visited[i]:
        # if not graph[i]:
        #     cnt += 1
        #     visited[i] = 1
        # else:
            dfs(i)
            cnt += 1

print(cnt)

DFS의 경우 리컬젼 리밋을 너무 적게 주거나 (예를 들어 1000)
리밋을 주지 않으면 런타임 에러(recursionError)가 발생한다.
그리고 sys.stdin.readline 대신 input을 쓰면 시간 초과가 발생한다.