백준 | 11724 연결요소의 개수

idea : 바이러스 문제랑 유사하게

링크드 리스트처럼 vector에 꼬리꼬리로 입력하기

6 5 1 2 2 5 5 1 3 4 4 6

 

이거같은 경우에는

이런 느낌으로 코드를 짜보려고 함

 

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>&v, vector<int>&visit, int st){
    visit[st] = true;

    for(auto x : v[st]){
        if(!visit[x]){
            visit[x] = true;
            dfs(v, visit, x);
        }
    }
}

int main(){
    int N, M, a, b;
    cin >> N >> M;
    vector<vector<int>> v(N+1);
    vector<int> visit(N+1, false);
    
    while(M--){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int ans = 0;
    for(int i = 1; i<=N; ++i){
        if(!visit[i]){
            ans++;
            dfs(v, visit, i);
        }
    }
    cout << ans;
    return 0;
}

 

한방에 성공!