BOJ(연결 요소의개수)11724

작성일 | In

11724 연결요소의 개수

  • 연결요소란 1~N가지의 정점으로 이루어져 있는 그래프가 나누어 존재할 경우, 각각의 그래프를 연결 요소라고 한다.

  • 연결 요소에 속한 모든 정점은 서로 연결하는 경로가 있어야 하며, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

  • DFS를 이용해서 1부터 탐색을 시작하며, DFS(1)이후에 check[i]=false로 나오면 연결 요소가 하나 더 있다는 뜻으로 해석했다.

  • 문제를 풀었는데 런타임 에러가 난다. python의 재귀 방식의 DFS로 재귀 제한에 걸려 런타임에러를 받게 된다고 한다. 따라서 스택으로 바꿔서 구현하거나, sys.setrecursionlimit을 통해 재귀 범위를 늘리면 된다.
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def DFS(s):
    visited[s] = True
    for next in arr[s]:
        if not visited[next]:
            DFS(next)
N, M = map(int, input().split())
# 인접리스트 생성
arr = [[] for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
visited = [False for i in range(N+1)]

cnt = 0
for i in range(1, N+1):
    if not visited[i]:
        DFS(i)
        cnt += 1
print(cnt)
  • 스택으로 바꿔서도 구현해봤다.
import sys
input = sys.stdin.readline

def DFS(s):
    visited[s] = True
    stack = [s]
    while stack:
        temp = stack.pop()
        for next in arr[temp]:
            if not visited[next]:
                stack.append(next)
                visited[next] = True

N, M = map(int, input().split())
# 인접리스트 생성
arr = [[] for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
visited = [False for i in range(N+1)]
cnt = 0
for i in range(1, N+1):
    if not visited[i]:
        DFS(i)
        cnt += 1
print(cnt)

참고자료 codeplus

0%