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

해당 문제는 1차원 배열을 이용하여 해결할 수 있는 문제이다.

 

dfs로 구현하였고, 헷갈리지만 않는다면 쉽게 풀 수 있다.

 

□ 소스코드

#include <bits/stdc++.h>

using namespace std;

vector<int> input11724[1001];
vector<bool> check11724(1001,false);

void dfs11724(int x){
    
    check11724[x] = true;
    
    for(int i=0;i<input11724[x].size();i++){
        int next = input11724[x][i];
        if(!check11724[next]){
            dfs11724(next);
        }
    }
}

void connect11724(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N,M; cin>>N>>M;
    
    for(int i=0;i<M;i++){
        int a,b; cin>>a>>b;
        input11724[a].push_back(b);
        input11724[b].push_back(a);
    }
    
    int result = 0;
    for(int i=1;i<=N;i++){
        if(!check11724[i]){
            result++;
            dfs11724(i);
        }
    }
    
    cout<<result<<"\n";
}

 

□ 유용한 반례

4 3
2 3
3 4
4 1
ANS: 1