[백준/c++] 11724번: 연결요소의 갯수

문제 링크 - https://www.acmicpc.net/problem/11724

🌱 문제

🌱 풀이

• DFS던 BFS던 상관없이 풀 수 있는 문제였다.
• for문을 돌면서 1~n번 정점에서 모두 dfs(or bfs)를 돌린다.
• 이때, 현재(i)번 정점이 아직 방문하지 않은 경우에만 answer++를 하고 dfs(or bfs)를 돌려야 한다.
• dfs(or bfs)를 돌면서 한 정점에 연결된 정점들은 모두 방문체크가 되므로, 방문하지 않은 정점을 발견하는 것이 연결요소 1개를 찾는 것이 된다.

🌱 코드

DFS로 푼 코드

//11724번: 연결 요소의 개수_dfs

/*
정점갯수 N, 간선 갯수 M
1<=N<=1,000
0<=M<=N(N-1)/2

*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int n,m;
vector<int> vec[10001];
bool check[1001];
int answer;

void dfs(int x){
    check[x]=true;
    
    for(int i=0;i<vec[x].size(); i++ ){
        int y=vec[x][i];
        if(check[y]==false){
            dfs(y);
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int u,v;
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    for(int i=1; i<=n; i++){
        if(check[i]==false){
            answer++;
            dfs(i);
        }
      

    }

    cout<<answer<<"\n";
}

BFS로 푼 코드

//11724번: 연결 요소의 개수_bfs

/*
정점갯수 N, 간선 갯수 M
1<=N<=1,000
0<=M<=N(N-1)/2

*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int n,m;
vector<int> vec[10001];
queue<int> q;
bool check[1001];
int answer;

void bfs(int x){
    q.push(x);

    while(!q.empty()){
        int y=q.front();
        q.pop();
        for(int i=0; i<vec[y].size(); i++){
            int z=vec[y][i];
            if(check[z]==false){
            q.push(z);
            check[z]=true;
            }
        }
    }
    
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int u,v;
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }

    for(int i=1; i<=n; i++){
        if(check[i]==false){
            answer++;
            bfs(i);
        }
      

    }

    cout<<answer<<"\n";
}