백준 11724 연결 요소의 개수

 

import sys

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

n, m = map(int, input().split())

connect = [[False] * n for _ in range(n)]

for _ in range(m) :
    x, y = map(int, input().split())
    connect[x-1][y-1] = True
    connect[y-1][x-1] = True

answer = 0
check = [False] * n

def dfs(i):
    for j in range(n):
        if not check[j] and connect[i][j] :
            check[j] = True
            dfs(j)

for i in range(n):
    if not check[i]:
        answer += 1
        check[i] = True
        dfs(i)


print(answer)

 

DFS를 이용해 해결했다.

 

체크 배열을 이용해 중복 체크를 방지하고, 재귀를 통해 연결된 노드를 검색 하도록 했다.