연결 요소 개수 세기
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 13번째.
연결 요소(connected component)는 모든 정점 쌍 사이에 경로가 존재하는 최대 정점 집합입니다. 간선이 없는 그래프는 정점의 수만큼 요소를 가지며, 완전히 연결된 그래프는 정확히 하나의 요소를 가집니다.
이를 세기 위해 모든 정점을 순회합니다. 아직 방문하지 않은 정점을 찾을 때마다 그것은 새로운 요소입니다. 카운터를 증가시킨 다음, 해당 정점에서 BFS 또는 DFS를 수행하여 도달 가능한 모든 정점을 방문한 것으로 표시합니다. 다음 방문하지 않은 정점으로 계속 진행합니다.
이 챌린지에서는 정점 리스트와 간선을 모두 제공합니다. 고립된 정점(간선이 없는 정점)도 여전히 자체적인 요소로 계산되므로 그 존재를 알아야 하기 때문입니다.
챌린지
쉬움2차원 정수 배열 adjacency와 정수 배열 vertices를 인자로 받아 그래프의 연결 요소(connected components)의 개수를 반환하는 countConnectedComponents 함수를 작성하세요.
그래프 구축 방법: 먼저 vertices의 모든 키에 대해 addVertex를 호출하여 고립된 정점들이 포함되도록 한 다음, adjacency의 모든 쌍에 대해 addEdge를 호출합니다. 그 후 모든 정점을 순회합니다. 방문하지 않은 각 정점은 새로운 연결 요소의 시작이 되므로 카운터를 증가시키고, 해당 정점에서 DFS/BFS를 수행하여 해당 연결 요소 전체를 방문한 것으로 표시합니다.
반드시 Graph 클래스를 사용해야 합니다 (graph에 제공됨). 인접 리스트를 모델링하기 위해 언어 내장 기능(맵, 셋 등)을 사용하지 마세요. 알고리즘을 위한 보조 데이터(방문 여부 확인을 위한 셋, 스택 등)는 표준 라이브러리 타입을 사용할 수 있습니다.
직접 해보기
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}