过家家
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
有 个小学生来玩过家家游戏，其中有 个男生，编号为 到 ，另外 个女生，编号也是 到 。每一个女生可以选择一个和她不吵嘴的男生来玩，除此之外，如果编号为 的女生的朋友（也是女生，且编号为 ）不和编号为 的男生吵嘴，那么 也可以选择 。此外，朋友关系是可以传递的，比如 和 是朋友， 和 是朋友，那么我们可以认为 和 也是朋友。注意，一个男生可以被多个女生选择为玩伴。
当每一位女生都选择了玩伴，那么他们会开始新一轮游戏。在每一轮后，每个女生都会开始去找一个新的男生做玩伴（以前没选过）。而且每一个女生最多能强制 个男生接受，无论他们以前是否吵嘴。
现在你的任务就是确定这 个小学生最多能玩几轮游戏。
输入格式
第一行有四个整数 （，，）。
表示有 个小学生，其中 个男生 个女生。
接下来 行，每行包含两个数字 表示编号为 的女生和编号为 的男生从没吵嘴过。
再接下来 行，每行包含两个数字 表示编号为 的女生和编号为 的女生是朋友。
输出格式
对于每组数据，输出一个整数，表示 个小学生最多能玩几轮。
4 5 1 2
1 1
2 3
3 2
4 2
4 4
1 4
2 3
3
并查集&最小生成树
- Status
- Done
- Problem
- 26
- Open Since
- 2025-8-10 13:30
- Deadline
- 2025-8-31 23:59
- Extension
- 24 hour(s)