[BOJ_11724] 연결 요소의 개수

연결 요소(Connected Component)의 개수를 구하는 문제입니다. 인접행렬을 이용해서 풀 수 있습니다.

인접 행렬의 요소를 모두 확인할 것인데(n * n) 시작 노드부터 dfs 함수에 넣고 확인하는데 한 회차를 다 돌면 return하고 연결 요소 카운트를 올립니다.

1부터 n까지를 반복하는데 방문하지 않은 곳만 dfs에 넣습니다.

n, m = map(int, input().split())
adj = [[0 for _ in range(n+1)] for _ in range(n+1)]
visited = [False] * (n+1)
result = 0

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

def dfs(cur):
    visited[cur] = True
    for i in range(1, n+1):
        if not visited[i] and adj[cur][i] == 1:
            dfs(i)
        if i == n:
            return

for i in range(1, n+1):
    if not visited[i]:
        dfs(i)
        result += 1

print(result)

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수