AtCoder Beginner Contest 288 C - Don't be cycle
求めたいものは削除する辺の本数の最小値です。
よってこれをとおくことにします。
削除する辺の本数の最小値(今回求めたいもの)
次に、任意の連結なグラフ(頂点)で、かつサイクルを持たないようなグラフの辺の最大数はであるという事実から、
連結なグラフが個の場合、残すことのできる辺の数は
であることがわかります。
グラフが閉路を持たないように辺を残すときの辺の最大数
よって最終的に求める答えは
で求まります。
#include <bits/stdc++.h> using namespace std; int main() { // 入力受け取り int N, M; cin >> N >> M; // インデックスと頂点番号を合わせるためにN+1としている vector<vector<int>> G(N+1); for (int i = 1; i <= M; i++) { int A, B; cin >> A >> B; G[A].push_back(B); G[B].push_back(A); } int S = 0; vector<bool> seen(N+1, false); // BFSで連結成分の個数を調べる for (int i=1; i<=N; i++) { if (seen[i] == false) { S++; queue<int> que; que.push(i); while (!que.empty()) { int q = que.front(); que.pop(); for (int v : G[q]) { if (!seen[v]) { seen[v] = true; que.push(v); } } } } } cout << M-N+S << endl; return 0; }