グラフが単純にする、すなわち自己ループと多重辺が存在しない状態にするために削除するべき辺を考えると、次の 2 通りが考えられます。

• \(u=v\) である辺 \((u,v)\) が存在する場合 : 自己ループなので必ず削除する必要があります。
• \(u \neq v\) である辺 \((u,v)\) が複数本存在する場合 : 多重辺なので 1 本だけ残してそれ以外を全て削除する必要があります。

よって、自己ループとなる辺は無条件に答えに本数を加算してよく、それ以外の辺については辺 \((u,v)\) が \(k\) 本存在するごとに \(k-1\) 本を答えに加算すればよいです。

実装には辺の種類ごとに登場する回数をカウントすることが出来ればよく、これは C++ の std::map などの辞書と呼ばれるデータ構造を用いれば高速にカウントできます。計算量は全体で \(\mathrm{O}(M \log M)\) 程度となり十分高速です。\(u \neq v\) の時に辺 \((u,v)\) と辺 \((v,u)\) を同一視する必要がある点に注意してください。

• 実装例(C++)

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

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  int ans = 0;
  map<pair<int, int>, int> m;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    if (u == v) {
      ans++;
      continue;
    }
    if (u > v) swap(u, v);
    m[{u, v}]++;
  }
  for (auto& [edge, k] : m) ans += k - 1;
  cout << ans << "\n";
}