[BOJ 11724] 연결 요소의 개수

문제는 여기에서 확인할 수 있다.

---

방향이 없는 그래프에서 연결 요소는 다음 두 조건을 만족하는 부분그래프이다.

• 부분그래프 내의 임의의 두 정점을 연결하는 경로가 항상 존재한다.

정점 i에 대해서, i로부터 DFS나 BFS를 수행한다면, 탐색 중에 지나는 모든 정점은 i가 속한 연결 요소의 정점이다.

이 성질을 이용해서 그래프를 탐색하면 된다.

#include<bits/stdc++.h>
 
using namespace std;
 
int N, M;
vector<int> v[1001];
bool c[1001];
 
void bfs(int i) {
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        c[x] = true;
        for (int y : v[x]) {
            if (!c[y]) {
                q.push(y);
                c[y] = true;
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    while (M--) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int rst = 0;
    for (int i = 1; i <= N; i++) {
        if (!c[i]) {
            rst ++;
            bfs(i);
        }
    }
    cout << rst;
    return 0;
}