[백준] 11724번 연결 요소의 개수 (파이썬)

풀이

# 시간 + 런타임 에러(재귀함수 늘리기) 발생을 막기 위해 sys 사용 필수
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline 

# dfs 풀이
def dfs(grap, num, visit):
    visit[num] = True

    for i in grap[num]:
        if not visit[i]:
            dfs(grap, i, visit)

# bfs 풀이
from collections import deque
def bfs(grap, num, visit):
    m = deque([num])

    visit[num] = True

    while m:
        q = m.popleft()

        for i in grap[q]:
            if not visit[i]:
                visit[i] = True
                m.append(i)

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

graph = [[]for _ in range(N + 1)]
# 방문 표시
visited = [False] * (N + 1)


for _ in range(M):
    u, v =  map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
# 방문표시가 안되있다면 다시 들어가도록 반복
for j in range(1, N + 1):
    if not visited[j]:
        dfs(graph, j, visited)
        bfs(graph, j, visited)
        cnt += 1

print(cnt)

BFS와 DFS 연습 겸 둘 다 사용해 보았다.
답은 둘 중 하나만 사용해도 나온다