[BOJ/백준 11724][C++] 연결 요소의 개수

문제

https://www.acmicpc.net/problem/11724

 

문제 내용

정점과 간선의 정보를 입력받아, 몇 개의 연결 요소로 이루어져 있는지 구하면 된다. (사이클을 말하는 게 아니라 연결 요소를 말하는 것)

 

문제 풀이

모든 노드에 대해 아직 방문하지 않은 경우, bfs를 돌리면 된다.

나는 이 문제를 인접 행렬로 구현하지 않고, 인접 리스트로 그래프를 구현했다.

 

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int n, m;
vector<int> arr[1001];
int visited[1001];

int main() {
    cin >> n >> m;

    int node1, node2;
    for (int i = 0; i < m; i++) {
        cin >> node1 >> node2;

        arr[node1].push_back(node2);
        arr[node2].push_back(node1);
    }

    queue<int> q;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i])
            continue;

        cnt++;
        q.push(i);
        visited[i] = cnt;
        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (auto next : arr[node]) {
                if (visited[next])
                    continue;
                q.push(next);
                visited[next] = visited[node];
            }
        }
    }

    cout << cnt;
    return 0;
}