11724번: 연결 요소의 개수

요즘 자주 실수하는데

0-based-index와 1-based-index일 때

for문과 if문이 어떻게 다른지 각별히 주의하자

 

bfs와 dfs 연습하시고

 

문제는 연결 요소의 개념만 알고 있으면 된다.

뭉텅이 하나를 연결 요소 하나라고 한다.

연결 요소끼리는 끊어져있다.

bfs/dfs를 이용해서 뭉텅이씩 bfs 돌리면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int ans = 0;
vector<int> graph[1001];
bool visited[1001];
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int tmp = q.front(); // back 아니다;;
        q.pop();
        for (int next : graph[tmp]) { // vector for문
            if (visited[next]) continue;
            visited[next] = true;
            q.push(next);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    // bfs
    for (int i = 1; i <= n; i++) { // 틀렸던 부분
        if (visited[i]) continue;
        bfs(i);
        ans++;
    }
    cout << ans;
}