[BOJ/11724번연결요소의개수] c++ / BFS

문제

정점과 간선의 개수가 주어지고, 연결요소의 개수를 구하는 문제

 

생각

전에 동아리할 때, 이런 문제 풀었었는데 기억이 안남 ..

vector쓰면 간편하게 풀리는 문제였음!!!!!!!!

-vector, size(), push_back() 개념 공부 필요..

 

문제풀이

1.vector 배열을 만들어줌

-1 2를 입력받으면, graph[1] 컨테이너에 2값이 저장됨

-1 4를 입력받으면, graph[1] 컨테이너에 4값이 저장됨

-graph[1]에는 2와 4값이 저장되어있고, 사이즈는 2임

2.BFS 탐색

-pop된 i, graph[i].size() 탐색하는데, 방문하지 않을 경우에만 push해줌

3.연결된 요소 개수를 카운터 해주면 됨

 

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M, u, v, cnt=0;
vector<int> graph[1001];
int vis[1001];
void BFS(int i) {
    queue<int> q;
    q.push(i);
    vis[i] = 1;
    while (!q.empty()){
        int cur = q.front(); q.pop();
        for ( int j = 0; j < graph[cur].size(); j++ ) {
            if ( vis[graph[cur][j]] ) continue;
            vis[graph[cur][j]] = 1;
            q.push(graph[cur][j]);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for ( int i = 0; i < M; i++ ) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for( int i = 1; i <= N; i++ ) {
        if ( vis[i] ) continue;
        BFS(i);
        cnt++;
    }
    cout << cnt;
}