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

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

11724번: 연결 요소의 개수

제목대로 연결 요소의 개수를 구하는 문제인데 배열 형태가 아니므로 각 정점을 인접 리스트로 구현해준다.

나는 int형 벡터를 갖는 배열로 구현하였다.

간선의 개수만큼 반복문을 실행하여 정점을 입력받아 u리스트에는 v를 추가하고 v리스트에는 u를 추가한다.

 

한 번 bfs를 시작할때 연결된 정점을 모두 방문한다. 즉, bfs가 한번 도는게 연결 요소 1개인 셈이다.

그러므로 모든 방문하지 않은 정점을 방문해서 bfs가 새로 실행될 때마다 ans값을 증가시켜주면 된다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
bool check[1000];
vector<int> list[1000];
 
void bfs(int x) {
    queue<int> q;
    q.push(x);
    check[x] = true;
 
    while(!q.empty()) {
        x = q.front();
        q.pop();
 
 
        //연결된 정점들을 검사
        for(int k=0; k<list[x].size(); k++) {
            int y = list[x][k];
            if(check[y] == false) {
                q.push(y);
                check[y] = true;
            }
        }
    }
}
 
int main() {
 
    int n,m;
    scanf("%d %d", &n,&m);
 
 
    //인접 리스트(벡터 배열로 구현)
    for(int i=0; i<m; i++) {
        int u, v;
        scanf("%d %d", &u,&v);
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    int ans = 0;
    for(int i=1; i<=n; i++) {
        if(check[i] == false) {
            ++ans;
            bfs(i);
        }
    }
 
    printf("%d", ans);
 
    return 0;
}