原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个可行的构造方案
1.2 题目背景、允许、禁止与限制
背景:
有 nnn 个栖息地和 mmm 条道路
允许:
要求将这些栖息地分配给三个团队
每个团队至少有 111 个栖息地
将若干栖息地归入一个团队之中后这些栖息地之间的路径将会被消除
求如何合理分配使得分配完毕后所有栖息地间均无环
1.3 题目数据范围与猜测
1≤n≤3×105⟶O(n log n)1 \le n \le 3\times 10^5 \longrightarrow O(n~log~n)1≤n≤3×105⟶O(n log n)
0≤m≤2n×4⟶这是非常重要的点!0 \le m \le 2n\times 4 \longrightarrow 这是非常重要的点!0≤m≤2n×4⟶这是非常重要的点!
1.4 一句话概括题意
有 nnn 个点,mmm 条边
将若干点归入一个集合中将会去除点之间所有边
构造一种合理的方案将这些点合理分配给三个团队后点之间不存在环
2 题目破题推导(分情况讨论)
3 模型匹配
求连通块数量是并查集
求返祖边是dfn
返祖边的两端合并也是并查集
4 最终代码(禁止抄袭,仅用于参考)
需要注意的点:
多测清空!凡是要多次用到的数组、变量一律清空
造极端hack数据:
📋 通用 Hack 思路(按优先级)
1️⃣ 边界值攻击
攻击点 数据构造 为什么有效
最小 n n = 1, n = 2 数组越界、除零、特殊判断遗漏
最大 n n = 3e5,链式图 递归爆栈、O(n²) 超时
m 最小/最大 m = 0 或 m = 2n-4 空图处理、边数上限
答案边界 强制输出 -1 的场景 无解判断错误
你的题目:n=3 且 m=2n-4=2,图是 1-2 和 2-3(树),答案是任意分配。如果代码假设 n>=3 但忘记处理特殊情况,就会炸。
2️⃣ 编号攻击(固定取点/取边的元凶)
这是最隐蔽也最高效的攻击方式。
攻击点 数据构造 为什么有效
固定取 1 和 2 让 1 和 2 在同一个环上 拆开环 → 保留环边 → 形成环
固定取 1 号点 让 1 号点是孤立点/特殊点 特殊处理错误
固定取前 m 条边 让前几条边恰好是"陷阱" 贪心策略失效
你的题目:让 1 和 2 在同一个三角形里,且还有第三个连通块 → 触发 cnt>=3 分支,固定把 1 和 2 拆开。
3️⃣ 结构攻击
攻击点 数据构造 为什么有效
链式图 1-2-3-...-n DFS 递归爆栈,或拓扑序出错
星形图 1 连所有点 中心节点特殊,贪心失效
完全图 所有点两两相连 边数上限检查遗漏
二分图 奇偶分组 染色/匹配类算法出错
三角形 1-2, 2-3, 3-1 环检测遗漏
重边 两条 1-2 去重逻辑出错
自环 1-1 特殊情况处理遗漏
你的题目:三角形 1-2-3-1 配合孤立点,触发编号攻击 + 环攻击的组合。
4️⃣ 随机+对拍(最暴力但最有效)
如果手造数据太麻烦,直接上随机生成 + 对拍