洛谷 P11829 分析（别看）
2026-08-19 18:33:45
发布于：天津
2阅读
0回复
0点赞
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个可行的构造方案
1.2 题目背景、允许、禁止与限制
背景：
有 个栖息地和 条道路
允许：
要求将这些栖息地分配给三个团队
每个团队至少有 个栖息地
将若干栖息地归入一个团队之中后这些栖息地之间的路径将会被消除
求如何合理分配使得分配完毕后所有栖息地间均无环
1.3 题目数据范围与猜测
1.4 一句话概括题意
有 个点， 条边
将若干点归入一个集合中将会去除点之间所有边
构造一种合理的方案将这些点合理分配给三个团队后点之间不存在环
2 题目破题推导（分情况讨论）
将n个点分成三个点集（每个点集中至少有一个点）
每个点集内部所有点之间的边去除
保证去除结束后整个图无环
分情况讨论：
1.若有三个及以上的连通块
将每一（或者更多）个连通块作为一个点集
2.若有两个连通块
较小的连通块成一个点集
较大的那个首先确保可以成为两个点集，那么如何确保选出的两个没有环？
可以在这个大连通块内分成1+若干个点
因为首先1个点不可能有环
其次那若干个点中假如有a<->1,b<->1是存在的，但是不存在a<->b，因此不可能有环
3.若有一个连通块
反祖边，如果发现某条边左右端点在一个集合里，说明这是反祖边（会导致成环）
需要去掉这些反祖边--每有一条反祖边，就将反祖边的两个端点放入一个点集中
这样的确能保证无环，但是万一无法组成剩余两个点集呢？
不会发生！
因为题目中给出：边的数量不超过2n-4
说明反祖边最多有(2n-4)-(n-1)=n-3条反祖边，相当于最多合并n-3次
初始有n个点集（每个点自成团体），每合并一次，少一个点集
那么进行完n-3次合并后，还有3个点集
那这3个点集自成3个团体即可
那如果这时候有>3个点集呢？没问题呀，只需要多个点集成一个团体
3 模型匹配
求连通块数量是并查集
求返祖边是dfn
返祖边的两端合并也是并查集
4 最终代码（禁止抄袭，仅用于参考）
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int num = 0;
int f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-'){
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
num = (num << 3) + (num << 1) + (ch ^ 48);
ch = getchar();
}
return num * f;
}
int t;
int n, m;
const int N = 3e5 + 10;
vector<int> g[N];
// 并查集部分
int fa[N];
int size[N];
void init(){
for (int i = 1;i <= n;i++){
fa[i] = i;
size[i] = 1;
}
}
int get(int x){
if (fa[x] != x){
fa[x] = get(fa[x]);
}
return fa[x];
}
void merge(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return;
if (size[x] < size[y]) swap(x, y);
fa[y] = x;
size[x] += size[y];
}
int query(){
int cnt = 0;
for (int i = 1;i <= n;i++){
if (fa[i] == i){
cnt++;
}
}
return cnt;
}
// 情况3所需并查集
int fa_3[N];
void init_3(){
for (int i = 1;i <= n;i++){
fa_3[i] = i;
}
}
int get_3(int x){
if (fa_3[x] != x){
fa_3[x] = get_3(fa_3[x]);
}
return fa_3[x];
}
void merge_3(int x, int y) {
x = get_3(x);
y = get_3(y);
if (x != y){
fa_3[y] = x;
}
}
//
pair<vector<int>, vector<int>> query2(){// 前面是数量少的，后面是数量多的
int mn = INT_MAX, mx = INT_MIN;
int mnn = -1, mxn = -1;
vector<int> mnv, mxv;
for (int i = 1;i <= n;i++){
if (fa[i] == i){
if (size[i] < mn){
mn = size[i];
mnn = i;
}
if (size[i] >= mx){
mx = size[i];
mxn = i;
}
}
}
for (int i = 1;i <= n;i++){
if (get(i) == mnn){
mnv.push_back(i);
} else if (get(i) == mxn){
mxv.push_back(i);
}
}
return make_pair(mnv, mxv);
}
struct edge{
int u, v;
};
vector<edge> back_edge;
int dfn[N], father[N];
int timer;
void dfs(int u, int f){
dfn[u] = ++timer;
father[u] = f;
for (int v : g[u]){
if (v == f) continue;
if (dfn[v] == 0){
dfs(v, u);
} else if (dfn[v] < dfn[u]){
back_edge.push_back({u, v});
merge_3(u, v);
}
}
}
signed main(){
t = read();
while(t--){
n = read(), m = read();
if (n < 3){
printf("-1\n");
continue;
}
init();
// 多测清空！！！
for (int i = 1;i <= n;i++){
g[i].clear();
}
for (int i = 1;i <= m;i++){
int a, b;
a = read(), b = read();
g[a].push_back(b);
g[b].push_back(a);
merge(a, b);
}
int cnt = query();
// printf("cnt:%d\n", cnt);
if (cnt >= 3){
vector<int> g1, g2, g3;
int root1 = -1, root2 = -1;
for (int i = 1;i <= n;i++){
if (get(i) == i){
if (root1 == -1){
root1 = i;
} else if (root2 == -1){
root2 = i;
} else {
break;
}
}
}
for (int i = 1;i <= n;i++){
if (get(i) == root1){
g1.push_back(i);
} else if (get(i) == root2){
g2.push_back(i);
} else {
g3.push_back(i);
}
}
printf("%lld ", g1.size());
for (int i = 0;i < g1.size();i++){
printf("%lld ", g1[i]);
}
printf("\n");
printf("%lld ", g2.size());
for (int i = 0;i < g2.size();i++){
printf("%lld ", g2[i]);
}
printf("\n");
printf("%lld ", g3.size());
for (int i = 0;i < g3.size();i++){
printf("%lld ", g3[i]);
}
printf("\n");
} else if (cnt == 2){
pair<vector<int>, vector<int>> temp = query2();
printf("%lld ", temp.first.size());
for (int num : temp.first){
printf("%lld ", num);
}
printf("\n");
printf("1 ");
printf("%lld\n", temp.second[0]);
printf("%lld ", temp.second.size() - 1);
for (int i = 1;i < temp.second.size();i++){
printf("%lld ", temp.second[i]);
}
printf("\n");
} else {
timer = 0;
memset(father, 0, sizeof(father));
memset(dfn, 0, sizeof(dfn));
back_edge.clear();
init_3();
dfs(1, -1);
vector<int> g1, g2, g3;
int root1 = -1, root2 = -1;
for (int i = 1;i <= n;i++){
if (get_3(i) == i){
if (root1 == -1){
root1 = i;
} else if (root2 == -1){
root2 = i;
} else {
break;
}
}
}
for (int i = 1;i <= n;i++){
if (get_3(i) == root1){
g1.push_back(i);
} else if (get_3(i) == root2){
g2.push_back(i);
} else {
g3.push_back(i);
}
}
printf("%lld ", g1.size());
for (int i = 0;i < g1.size();i++){
printf("%lld ", g1[i]);
}
printf("\n");
printf("%lld ", g2.size());
for (int i = 0;i < g2.size();i++){
printf("%lld ", g2[i]);
}
printf("\n");
printf("%lld ", g3.size());
for (int i = 0;i < g3.size();i++){
printf("%lld ", g3[i]);
}
printf("\n");
}
}
return 0;
}
需要注意的点：
多测清空！凡是要多次用到的数组、变量一律清空
造极端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️⃣ 随机+对拍（最暴力但最有效）
如果手造数据太麻烦，直接上随机生成 + 对拍
这里空空如也
有帮助，赞一个