有 $2n$ 个小学生来玩过家家游戏，其中有 $n$ 个男生，编号为 $1$ 到 $n$，另外 $n$ 个女生，编号也是 $1$ 到 $n$。每一个女生可以选择一个和她不吵嘴的男生来玩，除此之外，如果编号为 $X$ 的女生的朋友（也是女生，且编号为 $Y$）不和编号为 $Z$ 的男生吵嘴，那么 $X$ 也可以选择 $Z$。此外，朋友关系是可以传递的，比如 $a$ 和 $b$ 是朋友，$b$ 和 $c$ 是朋友，那么我们可以认为 $a$ 和 $c$ 也是朋友。注意，一个男生可以被多个女生选择为玩伴。
当每一位女生都选择了玩伴，那么他们会开始新一轮游戏。在每一轮后，每个女生都会开始去找一个新的男生做玩伴（以前没选过）。而且每一个女生最多能强制 $k$ 个男生接受，无论他们以前是否吵嘴。
现在你的任务就是确定这 $2n$ 个小学生最多能玩几轮游戏。
第一行有四个整数 $n,m,k,f$（$3 \le n \le 250$，$0 < m < n^{2}$，$0 \le f < n$）。
$n$ 表示有 $2n$ 个小学生，其中 $n$ 个男生 $n$ 个女生。
接下来 $m$ 行，每行包含两个数字 $a,b$ 表示编号为 $a$ 的女生和编号为 $b$ 的男生从没吵嘴过。
再接下来 $f$ 行，每行包含两个数字 $c,d$ 表示编号为 $c$ 的女生和编号为 $d$ 的女生是朋友。
对于每组数据，输出一个整数，表示 $2n$ 个小学生最多能玩几轮。
4 5 1 2 1 1 2 3 3 2 4 2 4 4 1 4 2 3
3
#include <bits/stdc++.h> #define AC return 0 using namespace std; int n, m, k, f, a[100000], num[100000], ans = 0x7f; bool mapp[500][500]; struct node { int from, to; } n1[100000], n2[100000]; int find(int x) { if (a[x] == x) return x; a[x] = find(a[x]); return a[x]; } void merge(int x, int y) { int fx = find(x); int fy = find(y); if (fx != fy) a[fy] = fx; } int main() { cin >> n >> m >> k >> f; for (int i = 1; i <= n; i++) a[i] = i; for (int i = 1; i <= m; i++) cin >> n1[i].from >> n1[i].to; for (int i = 1; i <= f; i++) cin >> n2[i].from >> n2[i].to; for (int i = 1; i <= f; i++) merge(n2[i].from, n2[i].to); for (int i = 1; i <= m; i++) if (!mapp[find(n1[i].from)][n1[i].to]) num[find(n1[i].from)]++, mapp[find(n1[i].from)][n1[i].to] = true; for (int i = 1; i <= n; i++) if (num[i]) ans = min(ans, num[i]); ans = min(n, ans + k); cout << ans << endl; AC; }