まず、この問題では「単純無向グラフ」「連結成分」のような少し聞きなれない単語が登場しますが、これらは グラフ理論 と呼ばれる分野の専門用語です。この問題は用語の意味に注をつけていますが、競技プログラミングではグラフ理論の用語がときどき説明なしに登場します。より多くの問題を解けるようになりたい人は、少なくとも Google 等の検索エンジンを利用して用語の意味を素早く把握できる能力を身につけましょう。

さて、連結成分の個数を求める方法を考えます。
頂点 \(v\) を 1 つ選んだ時に、\(v\) を含む連結成分に含まれる頂点の集合は 深さ優先探索(DFS) や 幅優先探索(BFS) のようなグラフ探索アルゴリズムを利用すれば調べることができます。
よって、次の手順で DFS や BFS を行えば全ての連結成分を 1 回ずつ探索することができます。

• はじめに、すでに訪問したかを管理する \(N\) 要素の配列 \(\text{visited}\) を false で初期化する。また、答えの値を管理する変数 \(\text{ans}\) を \(0\) で初期化する。
• \(i = 1, 2, \dots, N\) の順に次の操作を行う。
  • \(\text{visited}_i\) が true ならば何もしない。(頂点 \(i\) を含むはすでに訪問したので)
  • \(\text{visited}_i\) が false ならば「頂点 \(i\) を含む連結成分」を DFS や BFS 等で求め、連結成分に含まれるすべてに頂点 \(v\) について \(\text{visited}_v\) を true にする。そして \(\text{ans}\) に \(1\) を加算する。

例えばサンプル 1 (下図) ではおよそ次のような手順で連結成分を調べて行きます。

• 頂点 \(1\) は未訪問なので、頂点 \(1\) を含む連結成分を調べる。連結成分の頂点集合は \(\lbrace 1,2,3 \rbrace\) である。
• 頂点 \(2\) はすでに訪問したので調べなくてよい。
• 頂点 \(3\) はすでに訪問したので調べなくてよい。
• 頂点 \(4\) は未訪問なので、頂点 \(4\) を含む連結成分を調べる。連結成分の頂点集合は \(\lbrace 4,5 \rbrace\) である。
• 頂点 \(5\) はすでに訪問したので調べなくてよい。

計算量は \(\mathrm{O}(N + M)\) で、この問題を十分高速に解くことができます。

• DFS を利用した実装例

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> g;
vector<int> vis;

void dfs(int c) {
  vis[c] = true;
  for (auto& d : g[c]) {
    if (vis[d]) continue;
    dfs(d);
  }
}

int main() {
  cin >> N >> M;
  g.resize(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  int ans = 0;
  vis.resize(N);
  for (int i = 0; i < N; i++) {
    if (!vis[i]) ans++, dfs(i);
  }
  cout << ans << "\n";
}

• BFS を利用した実装例

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> g(N);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  int ans = 0;
  vector<int> vis(N);
  queue<int> Q;
  for (int i = 0; i < N; i++) {
    if (vis[i]) continue;
    ans++, vis[i] = true;
    Q.push(i);
    while (!Q.empty()) {
      int c = Q.front();
      Q.pop();
      for (auto& d : g[c]) {
        if (vis[d]) continue;
        vis[d] = true, Q.push(d);
      }
    }
  }
  cout << ans << "\n";
}

また、別解として Union-Find (素集合データ構造) と呼ばれるデータ構造を使う解法もあります。

• Union Find を利用した実装例

#include <iostream>
using namespace std;
#include "atcoder/dsu.hpp"
 
int main() {  
  int N, M;
  cin >> N >> M;
  atcoder::dsu uf(N);
  while(M--) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    uf.merge(u, v);
  }
  int ans = 0;
  for(int i = 0; i < N; i++) {
    if(uf.leader(i) == i) ans++;
  }
  cout << ans << "\n";
}