具有一定 Educational 意义。
题意：一张无向图，将其分解为若干组基环树森林，求至少需要分解多少组。
\(n, m\le 2000, \ \sum n, \sum m \le 2\times 10^4\)
充分利用基环树森林的性质：若为内向基环树，那么每个点的出边至多只有一条。
- 转化：我们相当于给图中的边定向，使得所有点出边数量最大值最小。
进一步的，等价于将每条边分配给两个点中的一个，使得所有点分配到的边数最大值最小。
考虑先二分答案，然后建立二分图模型：左部点表示边，右部点表示点。
跑二分图即可，时间复杂度 \(\mathcal O(m\sqrt n \log n)\)。
- 启示：对于一种知识结构模型，我们需要充分利用其本身的性质和特点，通过 发现 \(\to\) 知识模型 \(\to\) 性质 进行转化。
点击查看代码
#include <bits/stdc++.h>
namespace Initial {
#define ll int
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb push_back
#define i128 __int128
using namespace std;
const ll maxn = 1e5 + 10, inf = 2e9, mod = 998244353;
ll power(ll a, ll b = mod - 2, ll p = mod) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %p;
a = 1ll * a * a %p, b >>= 1;
} return s;
}
template <class T>
const inline ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
const inline void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
const inline void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
namespace Read {
char buf[1 << 22], *p1, *p2;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
template <class T>
const inline void rd(T &x) {
char ch; bool neg = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') neg = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(neg) x = -x;
}
} using Read::rd;
ll t, n, m, a[maxn], b[maxn];
struct Graph {
ll n, s, t, tot, head[maxn], cur[maxn];
struct edge {ll v, w, nxt;} e[maxn];
void ins(ll u, ll v, ll w) {
e[++tot] = (edge) {v, w, head[u]}; head[u] = tot;
e[++tot] = (edge) {u, 0, head[v]}; head[v] = tot;
}
ll dis[maxn], q[maxn], l, r;
bool bfs() {
for(ll i = 1; i <= n; i++) dis[i] = -1;
q[l = r = 1] = s, dis[s] = 0;
while(l <= r) {
ll u = q[l++];
for(ll i = head[u]; i; i = e[i].nxt) {
ll v = e[i].v, w = e[i].w;
if(w && dis[v] == -1) {
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
} return dis[t] >= 0;
}
ll dfs(ll u, ll flow) {
if(u == t) return flow; ll used = 0;
for(ll i = cur[u]; i; cur[u] = i = e[i].nxt) {
ll v = e[i].v, w = e[i].w;
if(w && dis[v] == dis[u] + 1) {
ll tmp = dfs(v, min(w, flow - used));
used += tmp, e[i].w -= tmp, e[i ^ 1].w += tmp;
if(flow == used) break;
}
} return used;
}
ll dinic() {
ll ret = 0;
while(bfs()) {
for(ll i = 1; i <= n; i++) cur[i] = head[i];
ret += dfs(s, inf);
} return ret;
}
void clr() {
for(ll i = 1; i <= n; i++) head[i] = 0;
tot = 1;
}
} G;
bool check(ll mid) {
G.clr(); G.n = G.t = n + m + 2, G.s = G.t - 1;
for(ll i = 1; i <= n; i++) G.ins(i, G.t, mid);
for(ll i = 1; i <= m; i++) {
G.ins(G.s, n + i, 1);
G.ins(i + n, a[i], 1);
G.ins(i + n, b[i], 1);
} return G.dinic() == m;
}
void solve() {
rd(n), rd(m);
for(ll i = 1; i <= m; i++) rd(a[i]), rd(b[i]);
ll lo = 0, hi = m;
while(lo <= hi) {
ll mid = lo + hi >> 1;
if(check(mid)) hi = mid - 1;
else lo = mid + 1;
} printf("%d\n", lo);
}
int main() {
rd(t); while(t--) solve();
return 0;
}