BOJ 11724 : 연결 요소의 개수

• 문제 링크 : boj.kr/11724
• 난이도 : S2
• 태그 : 그래프, BFS, DFS

11724번: 연결 요소의 개수

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<bool> visit(n+1);
    vector<vector<int>> e(n+1);

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(visit[i]) continue;
        ans++;
        queue<int> _q;
        _q.push(i);
        visit[i] = true;
        while(!_q.empty()) {
            int curr = _q.front(); _q.pop();
            for(auto u : e[curr]) {
                if(visit[u]) continue;
                _q.push(u);
                visit[u] = true;
            }
        }
    }
    cout << ans;

    return 0;
}

---

풀이

문제에서 연결 요소가 뭔지 알려주지 않아 접근에 어려움이 있다.

연결 요소란 간선으로 연결되어 있는 정점들의 집합을 말한다.

 

연결 요소의 수를 구해보자.

 

어떤 정점에서 탐색을 시작한다면, 그 정점과 같은 연결 요소에 속한 정점들은 탐색이 완료된다.

이미 탐색이 완료된 정점이라면 지금까지 찾은 연결 요소에 속해있었다고도 할 수 있다.

 

따라서 정점을 순회하며 아직 탐색하지 않은 정점이라면 그 정점을 출발지로 하여 탐색을 진행하고, 그 횟수를 세어 연결 요소의 개수를 구할 수 있다.

탐색은 DFS와 BFS중 편한 것을 골라 사용하면 된다.