[코딩테스트 C++] 연결 요소의 개수

오늘의 문제

연결 요소의 개수

문제 접근

• 덩어리의 개수를 찾는 흔한 그래프문제다.
• DFS를 통해 연결된 부분까지 true로 만들어준다.

나의 풀이

#include <iostream>
#include <vector>
using namespace std;
int m, n;
const int MAX = 100000;
vector<vector<int>> node(MAX);
bool visit[MAX] = {false, };

// 유기농 배추
void dfs(int in){
    visit[in] = true;
    for(int i=0;i<node[in].size();i++){
        if(visit[node[in][i]] == false)
            dfs(node[in][i]);
    }
}
int solution(){
    int answer = 0;
    for(int i=0;i<n;i++){
        if(visit[i] == false){
            dfs(i);
            answer++;
        }
    }
    return answer;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>> n >> m;
    int a, b;
    for(int i=0;i<m;i++){
        cin>>a >>b;
        node[a-1].push_back(b-1);
        node[b-1].push_back(a-1);
    }
    cout<< solution()<<endl;
    return 0;
}

다른 풀이

배울 점