연결 요소의 개수 (feat. 백준, 11724번)

연결 요소의 개수
https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <queue>
using namespace std;
int N;
set<int> arr[1001];
bool visit[1001];
int bfs(){
    register int count = 0;
    queue<int> q;
    for(register int n = 1; n <= N; ++n)
        if(!visit[n]){
            ++count;
            q.push(n);
            visit[n] = true;
            while(!q.empty()){
                auto p = q.front(); q.pop();
                for(auto& v : arr[p])
                    if(!visit[v])
                        visit[v] = true, q.push(v);
            }
        }
    return count;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(visit, false, sizeof(visit));
    register int M;
    cin >> N >> M;
    for(register int m = 0, u, v; m < M; ++m)
        cin >> u >> v, arr[u].insert(v), arr[v].insert(u);
    cout << bfs();
    return 0;
}
// *&)*@*

 

1. 방향 없는 그래프는 양방향으로의 접근이 가능한 그래프를 의미합니다.
2. 따라서 연결된 요소의 총 개수를 구하는 문제입니다.
3. 가령, 예제 1번을 보면 1-2-5 는 서로 연결되어 있고 3-4-6 또한 서로 연결되어 있습니다. 하지만 두 연결간 연결은 존재하지 않으므로 정답은 2 입니다.
4. 예제 2번을 보면 1~6 은 서로 연결되어 있습니다 (중간의 간선을 통해서). 따라서 정답은 1 입니다.