- 방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 DFS 완전 탐색 문제였다. 연결 요소는 나누어진 각각의 그래프를 말한다. 이 문제의 테스트케이스를 예로 들어 설명하면 다음과 같다.
6 5
1 2
2 5
5 1
3 4
4 6
2
- 첫 번째 그래프의 정점은 1, 2, 5이고 두 번째 그래프의 정점은 3, 4, 6이다.
- 따라서 연결 요소의 개수는 2개가 된다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def DFS(start, depth):
visited[start] = True
for i in graph[start]:
if not visited[i]:
DFS(i, depth+1)
N, M = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
u, v = map(int, input().strip().split())
graph[u].append(v)
graph[v].append(u)
visited = [False] * (N+1)
answer = 0
for i in range(1 ,N+1):
if not visited[i]:
DFS(i, 0)
answer += 1
print(answer)