백준 11724 연결 요소의 개수

과정

• 1차원 그래프의 DFS 사용했습니다.
• 왕복하는 항목이 있을 수 있으므로, U, V 양 쪽에 대해 간선을 고려해줬습니다.
• 재귀적으로 DFS를 진행했습니다.
• 다음은 처음 짠 코드입니다.

import sys
input = sys.stdin.readline
set.recursionlimit(10**8)

N, K = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(K):
    U, V = map(int, input().split())
    graph[U].append(V)
    graph[V].append(U)

visited = [False] * (N+1)
def bfs(x, graph, visited):
    global ans
    if visited[x]:
        return
    visited[x] = True
    ans += 1
    for i in graph[x]:
        bfs(i, graph, visited)

fin = 0
for i in range(1, N+1):
    if not visited[i]:
        bfs(i, graph, visited)
        fin += 1
print(fin)

• 다른 사람의 코드를 보고 수정한 코드입니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

N, K = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(K):
    U, V = map(int, input().split())
    graph[U].append(V)
    graph[V].append(U)

visited = [False] * (N+1)
def bfs(x, graph, visited):
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            bfs(i, graph, visited)

fin = 0
for i in range(1, N+1):
    if not visited[i]:
        bfs(i, graph, visited)
        fin += 1
print(fin)

• 재귀적으로 DFS를 실행할 때, DFS를 실행한 후에 모든 값에 대한 방문 여부를 확인하는 것보다, 방문하지 않은 값만 DFS를 실행하는 것이 시간이 2배 감소했습니다.