First of all, some of the terms in this problem may be unfamiliar, such as “simple directed graph” and “connected component”. These are technical terms in the field called graph theory. Although we explained the terms in this problem, a problem of competitive programming sometimes use the terms of graph theory without notes. If you want to solve more problems, at least learn to quickly grasp the meaning of the terms using a search engine like Google.

Now let us consider how to count the connected components.
When a vertex \(v\) is chosen, the set of vertices contained in the connected component that contains \(v\) can be found by a graph searching algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS).
Thus, you can inspect each connected component once by performing BFS or DFS as follows:

• First, initialize an \(N\)-element array \(\text{visited}\) with false, which is used to manage we have already visited each vertex. Also, initialize the variable \(\text{ans}\) with \(0\), which we use to manage the value of the answer.
• For each \(i = 1, 2, \dots, N\), do the following:
  • If \(\text{visited}_i\) is true, do nothing (because we have already visited vertex \(i\)).
  • If \(\text{visited}_i\) is false, find the “connected component that contains vertex \(i\)” with DFS or BFS, and set \(\text{visited}_v\) to true for every vertex \(v\) contained in the connected component. Then, add \(1\) to \(\text{ans}\).

For example, in Sample 1 (figure below), we inspect the connected components as follows, roughly:

• We have not visited vertex \(1\) yet, so we inspect the connected components that contains vertex \(1\). The vertex set of the connected component is \(\lbrace 1,2,3 \rbrace\).
• We skip vertex \(2\) because we have already visited.
• We skip vertex \(3\) because we have already visited.
• We have not visited vertex \(4\) yet, so we inspect the connected components that contains vertex \(4\). The vertex set of the connected component is \(\lbrace 4,5 \rbrace\).
• We skip vertex \(5\) because we have already visited.

The time complexity is \(\mathrm{O}(N + M)\), which is fast enough to solve this problem.

• Sample code using 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";
}

• Sample code using DFS

#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";
}

Alternatively, one can use a data structure called Disjoint set Union (or Union-Find).

• Sample code using Disjoint Set Union

#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";
}