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

Approach

다른 Component의 경우 DFS 탐색을 통해 방문할 수 없다는 점을 이용해주면 된다.

모든 정점에 대해서 방문하지 않았으면, dfs를 돌리고 component 개수를 1개씩 올려나가면 원하는 답을 도출시킬 수 있다.

component에 대해서는 다음 블로그를 참고하도록 하자.

https://m.blog.naver.com/kks227/220785731077

깊이 우선 탐색(Depth-First Search) (수정 2019-08-18)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int visited[1001];
vector<vector<int> > v(1001);

void dfs(int x){
    visited[x] = 1;
    for(int i = 0; i < v[x].size(); i++){
        int to = v[x][i];
        if(!visited[to]) dfs(to);
    }
    return;
}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    int n, m;
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int component_num = 0;

    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            dfs(i);
            component_num++;
        }
    }

    cout << component_num << "\n";
    return 0;
}