[BOJ_11724] 연결 요소의 개수

문제출처

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

dfs / bfs 두가지 모두 풀이가 가능하다. 하지만 분류가 bfs로 되어있어 bfs로 풀이하였다. bfs 개념을 익히는데 도움이 되는 문제

소스코드

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
int v, e;    //vertex, edge
int result;
bool visit[1001];
bool g[1001][1001];
void bfs(int s) {
    queue<int> q;
    q.push(s);
    visit[s] = 1;
    
    while (!q.empty()) {
        s = q.front();
        q.pop();
 
        for (int i = 1; i <= sizeof(g[s]); i++) {
            if (g[s][i] && !visit[i]) {
                q.push(i);
                visit[i] = 1;
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> v >> e;
    int start, end;
    // init graph...
    for (int i = 1; i <= e; i++) {
        cin >> start >> end;
        g[start][end] = 1;
        g[end][start] = 1;
    }
 
    for (int i = 1; i <= v; i++) {
        if (!visit[i]) {
            bfs(i);
            result++;
        }
    }
 
    cout << result;
    return 0;
}