백준 알고리즘 11724번 연결 요소의 개수(python)

기본적인 DFS & BFS 문제이다.

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(node):
    check[node] = 1
    for n in graph[node]:
        if check[n] == 0:
            dfs(n)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
cnt = 0
for i in range(1, N+1):
    if check[i] == 0:
        dfs(i)
        cnt += 1
print(cnt)

BFS 풀이

import sys
from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = 1
                queue.append(n)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
cnt = 0
for i in range(1, N+1):
    if check[i] == 0:
        check[i] = 1
        bfs(i)
        cnt += 1
print(cnt)