[DFS]백준11724번 연결 요소의 개수

백준 11724

연결 요소 (Connected Component) 란 연결된 그래프의 개수이다.

예를 들어 1-2-3 5-6 이 있다면, (1-2-3), (5-6) 은 각각 연결 요소 이기 때문에 연결 요소는 총 두 개이다.

만약 1-2-3-4-5 가 있다면, 연결 요소는 1이다.

DFS 나 BFS를 모두 이용할 수 있는 문제이다.

DFS 나 BFS 모두 탐색 알고리즘이기 때문에, 그래프가 연결되어 있다면 그래프를 처음부터 끝까지 순회한다. (순회의 순서는 다르지만)

따라서 전체 노드에 대해 반복문으로 방문하지 않은 노드에 대해서만 DFS, BFS를 수행하고, 순회한 노드(정점)을 표시한 뒤 DFS나 BFS 가 종료될 때만 count를 올려주면 쉽게 답을 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

vector<int> adj[1001];
bool visited[1001] = {false,};
void dfs(int n);
int main(){
    int N, M;
    cin >> N >> M;

    for(int i=0;i<M;i++){
        int one, two;
        cin >> one >> two;

        adj[one].push_back(two);
        adj[two].push_back(one);
    }
    int answer =0;
    for(int i=1;i<=N;i++){
        if(!visited[i]){
            answer++;
            visited[i] = true;
            dfs(i);
        }
    }
    cout << answer << endl;
}

void dfs(int n){
    visited[n] = true;
    for(int i=0;i<adj[n].size();i++){
        if(!visited[adj[n][i]]){
        visited[adj[n][i]] = true;
        dfs(adj[n][i]);    
        }
    }
}