[BOJ] #11724 연결 요소의 개수

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

11724번: 연결 요소의 개수

---

BFS를 순회하면서 연결 요소의 갯수가 있는지 찾는 문제다. 처음엔 문제를 잘못 읽고 연결된 그래프가 몇개인지만 세아려서 출력하면 되는줄 알았는데, 아무 간선도 가지지않는 정점도 연결 요소에 포함시켜 구현해야 했다.

방향성 없고 가중치 없는 그래프다 보니 그냥 바로 BFS로 감을 잡고 풀었고, 백준 2606번 바이러스 문제와 유사한 부분이 많은 문제였다.

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

#define MAX 1005

using namespace std;

vector<int> Graph[MAX];
int visited[MAX];
int cnt = 0;
bool flag;

void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int n = q.front();
        q.pop();

        for (int i=0; i<Graph[n].size(); i++) {
            int idx = Graph[n][i];

            if (!visited[idx]) {
                q.push(idx);
                visited[idx] = true;
                flag = true;
            }
        }
    }
}

int main() {
    int N,M;
    cin >> N >> M;

    for (int i=0; i<M; i++) {
        int a,b;
        cin >> a >> b;

        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }

    for (int i=1; i<=N; i++) {
        if (visited[i]) continue;
        else {
            BFS(i);

            if (flag == true) cnt++;
        }

        if (flag == false) cnt++;
    }

    cout << cnt << '\n';

    return 0;
}

간선없는 정점을 포함시키지 않아서 첫번째 시도는 틀렸었다.