[백준] 11724번: 연결 요소의 개수 - C++

[백준] 11724번: 연결 요소의 개수 - C++

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

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

출력 첫째 줄에 연결 요소의 개수를 출력한다.

그래프 탐색 알고리즘을 이용하여 푸는 문제.

DFS를 사용하여 풀었다. 0번 정점부터 N까지 한번씩 DFS를 실행하되, DFS에서 새로 정점을 방문할 때 마다 c를 1씩 증가시켜 방문한 노드의 수를 세주고, DFS가 끝났을 때 방문한 노드의 수 c가 이전보다 증가했다면 새로운 그래프가 존재한다는 의미이므로 count 를 1 증가시켜준다.

최종적으로 count에 기록된 수가 연결 요소의 개수가 된다.

코드

#include #define MAX 1001 using namespace std; int graph[MAX][MAX] = { 0 }; bool visited[MAX] = { false }; void DFS(int vertex, int V, int& C); int main(void) { int n, m; scanf("%d %d", &n;, &m;); for(int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a;, &b;); graph[a][b] = graph[b][a] = 1; } int c = 0, count = 0, i = 1; while(c != n) { int temp = c; DFS(i, n, c); if(temp < c) count++; i++; } printf("%d

", count); return 0; } void DFS(int vertex, int V, int& c) { if(!visited[vertex]){ visited[vertex] = true; c++; } for(int i = 1; i <= V; i++) { if(visited[i] || graph[vertex][i] == 0) continue; DFS(i, V, c); } }

from http://miiinnn23.tistory.com/49 by ccl(A) rewrite - 2021-12-22 22:26:31