💡문제 분석 요약

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램

입력

첫째 줄 : 정점의 개수 $N$, 간선의 개수 $M$

• 1 ≤ $N$ ≤ 1,000
• 0 ≤ $M$ ≤ ${N(N-1)} \over 2$

둘째 줄 ~ $M$개 : 간선의 양 끝 점 u, v

• 1 ≤ u, v ≤ $N$, u ≠ v
• 같은 간선은 한 번만 주어짐

출력

연결 요소의 개수

• 예제
• 추가 엣지 케이스

<aside> 📎 https://www.acmicpc.net/problem/11724

</aside>

💡알고리즘 설계

1. 인접리스트를 이용하여 그래프 초기화
2. dfs 사용하여 탐색 (start_node = 1
   1. node와 인접한 노드 방문
   2. 방문 완료시 더 이상 방문하지 않도록 이를 표기할 수 있는 무언가 조치 취하기

💡코드

import sys
from collections import defaultdict

v, e = map(int, sys.stdin.readline().strip().split())
graph = defaultdict(list)

for _ in range(e):
    a, b = map(int, sys.stdin.readline().strip().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(node):
    if node not in visited:
        visited.add(node)
        for next in graph[node]:
            dfs(next)
        return 1
    return 0

visited = set()
cnt = 0
for idx in range(v):
    cnt += dfs(idx + 1)

print(cnt)

💡시간복잡도

그래프 초기화 $O(e)$

모든 노드 방문(dfs) $O(v + e)$