[알고리즘] 백준 - 연결 요소의 개수 (python 파이썬)

hj·2021년 5월 11일
0

알고리즘

목록 보기
8/35
post-thumbnail
post-custom-banner

백준 - 연결 요소의 개수

설명

  • 연결 리스트, DFS, 스택으로 구현

풀이

  • 백준 재귀 제한 때문에 sys.setrecursionlimit(10000) 추가
import sys
from sys import stdin

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

graph = { key + 1: [] for key in range(n) }
for _ in range(m):
    a, b = map(int, stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(i, dis):
    stack = [i]

    while stack:
        v = stack.pop()
        if v not in dis:
            dis.append(v)
            for w in graph[v]:
                stack.append(w)
    return dis



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

print(cnt)
post-custom-banner

0개의 댓글