먼저, 연결요소란 그래프의 개수와 같다. 정점 사이에 겹쳐진게 없고, 나누어진 각각의 그래프를 연결 요소라고 생각하면 된다. 연결 요소는 dfs나 bfs탐색으로 구할 수 있다.
graph는 2차원 배열로 연결된 정보를 얻을 수 있음. visited 배열은 정점에 방문했는지 확인하기 위한 배열로 False로 초기화.
dfs함수에서는 방문하지 않은 곳을 dfg해주고 반복 끝에 result값에 1을 더하고 출력하면 됨.
이 과정을 수행할 수 없을 때까지 반복한다.
visited = [False] * 4
graph = [
[],
[1,3],
[2],
[2,3]
]
def dfs(graph, v, visited):
visited[v] = True # 현재 노드 방문 처리
print(v, end = ' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph, 1, visited)
# 결과
1 3 2
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
visited=[False]*(n+1)
count = 0
for _ in range(m):
u,v=map(int,input().split())
graph[u].append(v)
graph[v].append(u)
def dfs(v):
visited[v]=True
for i in graph[v]:
if not visited[i]:
dfs(i)
for i in range(1,n+1):
if not visited[i]:
dfs(i)
count += 1
print(count)