11724. 연결 요소의 개수

문제

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

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

예시

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

output
2

input
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

output
1

풀이

import sys
sys.setrecursionlimit(10**7)

N, M = map(int, sys.stdin.readline().split())

adj = [[] for _ in range(N + 1)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    adj[u].append(v)
    adj[v].append(u)
    
def dfs(src):
    visited[src] = 1
    for node in adj[src]:
        if visited[node] == 0:
            dfs(node)
        
ans = 0
visited = [False] * (N + 1)
for i in range(1, N + 1):
    if not visited[i]:
        dfs(i)
        ans += 1
        
print(ans)

그래프와 관련된 아주 기본 문제이다. 두번째 줄부터 주어지는 각 연결 요소로 이루어진 그래프의 연결 요소의 개수를 구하는 문제로 모든 노드를 탐색하면서 연결된 그래프의 개수를 구하면 된다.

dfs를 사용하여 문제를 해결할 수 있었고 노드를 방문하게 되면 해당 노드와 연결되어져 있는 모든 노드들을 탐색하게 되고 결국 주어진 연결 요소가 몇 개의 그래프로 이루어져 있는지 구할 수 있다.

항상 사용하지만 visited 리스트를 사용해서 dfs로 탐색하는 모든 노드의 방문을 기록하고 방문하지 않은 노드만을 탐색하게 되면서 연결 요소의 개수를 구할 수 있다.