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

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

BOJ - 연결 요소의 개수

문제 유형: 그래프, bfs

문제 난이도: Silver II

시간 제한: 3초

메모리 제한: 512MB

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

풀이

처음 방문하는 노드에서 bfs/dfs를 돌리면 그 노드가 소속된 컴포넌트는 모두 방문처리된다. 이를 이용해서 탐색하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m;
  vector<vector<int>> graph(n + 1);
  vector<bool> visited(n + 1, false);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
  }

  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (!visited[i]) {
      queue<int> q;
      q.push(i);
      visited[i] = true;
      while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (const auto &next : graph[curr]) {
          if (!visited[next]) {
            visited[next] = true;
            q.push(next);
          }
        }
      }
      ans++;
    }
  }

  cout << ans << "\n";

  return 0;
}