BOJ 11724번 연결 요소의 개수

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/11724/11724/%EC%86%8C%EC%8A%A4.cpp

 

연결요소의 개수를 파악하라는 것은

전체 그래프의 개수를 구하라는 것이다.

모든 정점이 다 연결된게 아닐수도 있으니 끊어져있는 경우 개수를 증가시키라는 말이다.

코드포스할때 하모니 그래프 문제를 풀었던 기억이 있는데

이 문제가 기본 베이스가 되지 않을까 생각한다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int N, M, s, e;
vector<int> v[1001];
bool visit[1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> s >> e;
        v[s].push_back(e);
        v[e].push_back(s);
    }
 
    int cnt = N, start, sum = 0;
    queue<int> q;
    
    while (cnt) {
        sum++;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                start = i;
                break;
            }
        }
        q.push(start);
        while (!q.empty()) {
            int num = q.front();
            q.pop();
 
            if (visit[num]) continue;
            visit[num] = 1;
            cnt--;
 
            for (int i = 0; i < v[num].size(); i++) {
                if (visit[v[num][i]] == 0) q.push(v[num][i]);
            }
        }
    }
 
    cout << sum;
    return 0;
}