그래프에서 연결 요소의 개수 구하기 (파이썬 코드)

  아래 그래프에는 3개의 연결 요소가 있다.

 

 

  연결 요소의 개수를 세는 코드는 다음과 같다.

 

n = 6
m = 4
# 그래프 정보 초기화
graph = [
    [1, 2],
    [0, 2],
    [0, 1],
    [4],
    [3],
    []
]
# 각 노드의 방문 여부
visited = [False] * n

# 특정 노드에서부터 연결된 모든 노드를 방문 처리
def dfs(x):
    visited[x] = True
    # 현재 노드와 인접한 노드 또한 방문 처리
    for i in graph[x]:
        if not visited[i]:
            dfs(i)

result = 0
for i in range(n):
    # 아직 방문하지 않았다면 방문
    if not visited[i]:
        dfs(i)
        result += 1
print(result)