[백준/C++] 연결 요소의 개수

11724번: 연결 요소의 개수 (acmicpc.net)

11724번: 연결 요소의 개수

문제유형

*깊이 우선 탐색
*너비 우선 탐색

문제

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

입출력 예제

(입력 1)	6 5 1 2 2 5 5 1 3 4 4 6
(출력 1)	2
(입력 2)	6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3
(출력 2)	1

풀이

1. 먼저 이번 문제를 DFS방식으로 풀어보자면, 무방향 그래프에서 방문하지 않은 노드를 탐색한다.

2. 노드를 탐새학면서 연결된 모든 노드를 방문을 하고, 각 요소들을 찾아서 cnt값을 증가시킨다.

3. 마지막으로 구성 요소의 개수를 출력한다.

코드

 

#include <iostream>
#include <vector>

using namespace std;

int N, M, cnt=0;
bool visited[1001];
vector<int> graph[1001];

void DFS(int node) {
    visited[node]=true;
    for (int i=0; i<graph[node].size(); i++) {
        int idx = graph[node][i];
        if (!visited[idx]) {
            DFS(idx);
        }
    }
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    for (int i=1; i<=N; i++) {
        if (!visited[i]) {
            cnt++;
            DFS(i);
        }
    }
    
    cout << cnt << "\n";
     
    return 0;
}