백준 11724번, 연결 요소의 개수

백준 11724번 c++ 문제풀이

문제:

백준 11724

풀이:

1. 이차원 벡터에 간선 끼리 연결되어있는 정점의 정보를 입력한다.
2. dfs 함수를 통해 어떤 요소끼리 연결되어 있는지 판단한다.
3. dfs 함수가 끝났을 때도 방문하지 않은 노드가 있다면, 그 노드부터 다시 dfs함수를 실행한다.
4. 총 몇번 함수를 돌렸는지 확인하고 출력한다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

void dfs(int start, vector<int> v[], bool visited[]){
    visited[start] = true;

    for(int i=0;i<v[start].size();i++){
        if(!visited[v[start][i]]){
            dfs(v[start][i], v, visited);
        }
    }
}

int main(){

    int n,m;

    cin >> n >> m;

    vector <int> v[n+1];
    bool visited[n+1] = {0, }; //해당 노드에 방문했는지 판별

    for(int i=0;i<m;i++){
        int input1, input2;
        cin >> input1 >> input2;

        v[input1].push_back(input2);
        v[input2].push_back(input1);
    }
    int start = 1;
    int result = 0;
    for(int i=1;i<=n;i++){
        if(visited[i] == false){
            dfs(i, v, visited);
            result++;
        }
    }
    
    cout << result;
    return 0;
}

감사합니다.