問題で問われているのは削除する必要のある辺の本数の最小値ですが、残すことのできる辺の本数の最大値について考えます。最大で \(L\) 本の辺を残すことができるとすると、元の問題の答えは \(M-L\) です。

ここで、グラフの連結成分の個数を \(S\) とおきます。各連結成分について、何本の辺を残せるでしょうか。頂点数が \(X\) の連結成分について考えると、適当な全域木を取ることにより \(X - 1\) 本以上は残すことができます。一方、\(X\) 本以上の辺を残すことはできません。これは辺のない状態から閉路ができないよう \(X\) 本以上の辺を追加していくことを考えると、連結成分の個数が減る操作が \(X\) 回以上行われてしまうことからわかります。

したがって、各連結成分の大きさを \(X_1,X_2, \ldots, X_S\) とすると、\(L = \displaystyle \sum_{i=1}^{S}(X_i-1)\) です。\(N = \displaystyle \sum_{i=1}^{S} X_i\) だったので、\(L = N - S\) です。

以上より、元の問題の答えは \(M - N + S\) であったことがわかりました。連結成分の個数は DFS や BFS 、UnionFind などを用いて数えることができます。

実装例 ( BFS を用いた解法 )

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>());
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	vector<bool> used(n);
	int s = 0;
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			s++;
			queue<int> que;
			que.push(i);
			while (!que.empty()) {
				int q = que.front(); que.pop();
				for (int v : graph[q]) {
					if (!used[v]) {
						used[v] = true;
						que.push(v);
					}
				}
			}
		}
	}
	cout << m - n + s << '\n';
}

実装例 ( ACL を用いた実装が軽い解法 )

#include <iostream>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main() {
	int n, m;
	cin >> n >> m;
	dsu d(n);
	int ans = 0;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		if (d.same(u, v)) ans++;
		d.merge(u, v);
	}
	cout << ans << '\n';
}