[백준] 11724번 연결 요소의 개수

💡문제접근

• 방향 없는 그래프가 주어졌을 때, 연결 요소(Connected Component)의 개수를 구하는 DFS 완전 탐색 문제였다. 연결 요소는 나누어진 각각의 그래프를 말한다. 이 문제의 테스트케이스를 예로 들어 설명하면 다음과 같다.

💡테스트케이스

입력

6 5
1 2
2 5
5 1
3 4
4 6

출력

2

• 첫 번째 그래프의 정점은 1, 2, 5이고 두 번째 그래프의 정점은 3, 4, 6이다.
• 따라서 연결 요소의 개수는 2개가 된다.

💡코드(메모리 : 65296KB, 시간 : 760ms)

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)

💡소요시간 : 12m