(C++) 백준 11724번 - 연결 요소의 개수

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

11724번: 연결 요소의 개수

풀이

방향이 없는 그래프를 BFS 하여 풀이하였다.

BFS를 사용하여 하나의 정점부터 차례대로 순회하면 이것들은 하나의 연결 요소가 된다.

그렇기에 출발점을 정점 하나하나로 두고, 방문했는지 여부를 사용하면 연결 요소의 수까지 파악할 수 있다.

#include <iostream>
#include <queue>

using namespace std;

vector<int> gp[1002];
int visited[1002];
int n, m, u, v, num;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    while(m--){
        cin >> u >> v;
        gp[u].push_back(v);
        gp[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        if(visited[i]) continue;
        visited[i] = 1;
        num++;
        queue<int> q;
        q.push(i);
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            for(auto k : gp[cur]){
                if(visited[k]) continue;
                q.push(k);
                visited[k] = 1;
            }
        }
    }
    cout << num;
}