[백준] 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 <cstdio>
#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\n", 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);
    }
}