[BOJ] 연결 요소의 개수

---

코드

import sys
input = sys.stdin.readline


def dfs(node):
    visited[node] = True   # 방문처리
    for a in adj[node]:    # 방문하지 않은 인접 노드들을 방문
        if visited[a] == False:
            dfs(a)


N, M = map(int, input().split())    # 정점, 간선 개수
adj = [list() for _ in range(N+1)]  # 인접 노드 리스트
visited = [False for _ in range(N+1)]    # 방문여부

# 인접노드 저장
for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)


component = 0
for i in range(1, N+1):
    if visited[i] == False:    # 방문하지 않은 노드에 대해 dfs 수행
        dfs(i)
        component += 1

print(component)
        

결과

풀이 방법

• 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있는데 이때 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라고 부른다.
• 연결 요소이려면 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 하며, 다른 연결 요소의 정점과 연결하는 경로가 존재해서는 안 된다.
• 연결 요소를 탐색하는 방법에는 DFS와 BFS가 있다.
• 인접 노드 리스트와 방문여부 리스트를 활용하여 방문하지 않은 노드에 대해 dfs를 수행하고 한 번 수행할 때마다 연결 요소의 개수를 증가시킨다.

---