연결 요소

연결 요소란?

무방향 그래프에서 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프를 연결 요소라고 한다.

예를 들어, 다음 그림에서 연결 요소의 갯수는 2개이다.

풀이 방법

DFS나 BFS로 풀 수 있다.

DFS로 풀기

• 정점의 갯수만큼 1부터 DFS를 돌린다.
• 방문하지 않은 노드가 있으면 그 노드로 이뤄진 그래프는 또 다른 연결요소가 되므로 반복문을 돌려주며 dfs한 횟수를 더해준다.