最適に辺を削除した時に、削除せずに残すことが可能な辺の本数に注目しましょう。
与えられるグラフが \(K\) 個の連結成分 \(C_1, C_2, \dots, C_K\) に分かれているとします。この時、各 \(C_i\) ごとに \(|C_i| - 1\) 本の辺を残すことができて、これが最大です。よって、残すことができる辺の本数の最大は、\(\sum_{i=1}^K C_i = N\) であることも合わせると、

\[ \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} \]

となります。これが残すことができる辺の本数の最大なので、元のグラフを森にするために削除すべき辺の本数の最小値は

\[M - (N - K)\]

となります。よって、連結成分の個数 \(K\) が求まればこの問題を解くことができるとわかりました。

連結成分の個数を数える問題は ABC284 の C 問題 ですでに取り上げました。上記の問題の解説を読めばわかる通り、連結成分の個数は DFS や BFS などのグラフ探索アルゴリズムか素集合データ構造(Union-Find) を用いれば高速に個数を求めることができます。

以上の考察によりこの問題を解くことができました。計算量は \(\mathrm{O}(N + M)\) や \(\mathrm{O}((N+M) \alpha(N))\) (\(\alpha(N)\) はアッカーマン関数の逆関数) 程度で十分高速です。

• 実装例(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";
}