How many edges can be retained when edges are removed optimally?
Suppose that the given graph consists of \(K\) connected components \(C_1, C_2, \dots, C_K\). Then, for each \(C_i\) we can retain \(|C_i| - 1\) edges, which is the maximum possible. Together with \(\sum_{i=1}^K C_i = N\), the maximum number of edges that can be retained is

\[ \begin{aligned} &\sum_{i=1}^K \left(\vert C_i \vert - 1\right) \\ &= \sum_{i=1}^K \vert C_i \vert - \sum_{i=1}^K 1 \\ &= N - K. \end{aligned} \]

Therefore, the minimum number of edges required for the original graph to become a forest is

\[M - (N - K).\]

Thus, the problem can be solved if we can find the number of connected components \(K\).

Counting connected components is already asked in ABC284, Problem C. As explained in the editorial for this problem, the number of connected components can be counted fast by graph searching algorithms like DFS (Depth-First Search) or BFS (Breadth-First Search), or Disjoint Set Union.

By this observation, the problem has been solved. The complexity is about \(\mathrm{O}(N + M)\) or \(\mathrm{O}((N+M) \alpha(N))\) (where \(\alpha(N)\) is the inverse Ackerman function), which is fast enough.

• Sample code (C++)

#include <iostream>
using namespace std;
#include "atcoder/dsu.hpp"

int main() {
  int N, M;
  cin >> N >> M;
  atcoder::dsu uf(N);
  int K = N;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    if (!uf.same(u, v)) uf.merge(u, v), K--;
  }
  cout << M - (N - K) << "\n";
}