如果让我从 PAT 乙级里挑一道“看着不算难、提交时却最容易翻车”的题，我第一个想到的往往就是 1090：危险品装箱。题面非常直白，先给你一批不能放在同一个集装箱里的危险品编号配对，再给你若干个集装箱的货物清单，让你判断每个箱子会不会“出事”。但就是这道题，存储方式、输入方式、边界处理稍微差一点，就可能在评测机上换来一个又一个非零返回或者超时。这篇就当是踩坑复盘，把题目拆解、数据结构选型、完整代码和几个隐蔽测试点都揉在一起讲，希望正在刷乙级的朋友能直接拿去用。
1. 题目拆解：危险品装箱到底让我判断什么
1.1 输入格式里的两个关键数字：N 和 M
题目输入第一个正整数 N，表示危险品配对数量；第二个正整数 M，表示待检查的集装箱数量。接下来有 N 行，每行两个正整数 a 和 b，表示编号为 a 的危险品和编号为 b 的危险品不能放在同一个箱子里。注意这里的“编号”是危险品的货物编号，不是行号，也不是什么连续编号，它本质上就是一个标识符。最后是 M 个箱子，每个箱子先给一个整数 K，表示这个箱子一共有 K 件货物，后面紧跟 K 个货物编号。
这里有个很多人第一眼容易忽略的点：N 和 M 是两类完全不同的输入量，N 管的是“危险关系表”，M 管的是“装箱查询表”。读数据的时候不能把它们搞混，尤其是后续用循环去读配对时，循环次数写错会直接导致读取错位，后面所有箱子的判断全部变成“看运气”。早期我练这题时，曾经在测试一个只有 1 对危险配对、但箱子数量很多的数据时，把配对读取循环写成了 M 次，结果第二个箱子开始读到的东西全是乱的，输出结果自然无法解释。
1.2 一个箱子安全，到底要满足什么条件
一个箱子要输出 Yes，意思是箱子里的所有货物可以共存，不存在任意一对“危险配对”。只要箱子中存在任意一对货物编号，它们出现在题目给定的危险配对列表中，箱子就必须输出 No。
举个例子。假设危险配对是：
1 2 3 4那么箱子[1, 2]是不安全的，箱子[1, 3]是安全的，箱子[4, 3]因为 3 和 4 是危险配对，也不安全。这里很容易形成的第一版思路是：把每个箱子里面的货物两两组合，检查这个组合是否出现在危险配对集合里。这种做法正确性没有任何问题，但复杂度是 O(K^2)，每个箱子都要做 K 的平方次判断。如果 K 达到几百甚至几千，M 再大一点，超时几乎是可以预见的。
所以正确思路应该是“反向查”：给每个货物维护一份它的危险邻居列表，读箱子时先把箱子里的货物编号放进一个集合，然后遍历箱子里的每个货物 x，看看 x 的危险邻居里有没有某个编号也出现在这个集合中。只要命中一次，这个箱子就不安全。
1.3 最容易忽略的一句话：危险配对不分方向
题目里说 a 和 b 不能同箱，那 b 和 a 自然也不能同箱。这个关系是双向的，没有方向性。在代码里，如果你只把 b 塞进forbid[a]的列表，却没有把 a 塞进forbid[b]的列表，判断时就可能出现“箱子遍历到哪个货物先看，结果就不一样”的诡异现象。比如箱子[b, a]，你先遍历到 b，若 b 的危险邻居里没有 a，就会误判成 Yes。这种错误在真机上非常难发现，因为你换一组数据排序，结论可能又变对了。最稳妥的做法是在建表时就严格双向写入。
2. 存储与查询方案：怎么组织“危险名单”才算体面
2.1 数组下标法：很多人第一版写法，也是翻车重灾区
看到货物编号是正整数，很多人第一反应是直接开一个大数组，用编号当下标。比如vector<int> forbid[100005]，然后读入 a、b 时执行forbid[a].push_back(b); forbid[b].push_back(a);。这种做法在编号范围固定且不大的题目里确实能过，但它的脆弱点非常明显：一旦你记不清题目给的数据范围上限，数组开小了就是运行时错误，开太大又会浪费内存；更麻烦的是，你还需要另一个标记数组来记录“当前箱子出现了哪些货物”，每次处理完一个箱子后还要把用过的标记位重新清回 false。清不干净的话，上一个箱子的货物就会“残留”到下一个箱子，造成串味误判。
我之前就干过这种事。第一次用数组标记法写完，本地测试三个箱子，第一个箱子不安全，第二个箱子内容其实是安全的，但因为第一个箱子标记位没清，把前一个箱子的编号也算进去了，输出成了 No。这种逻辑错误比编译错误难定位得多，因为它不是每次都错，只在箱子之间有重复编号或者相邻编号时才会触发。
2.2 哈希表建邻接表：不依赖编号范围的稳妥解法
更通用的方案是用哈希表建邻接表。在 C++ 里可以用unordered_map<int, unordered_set<int>>，在 Python 里用字典加set()。这样货物编号是多少都无所谓，哪怕编号跳到十万、百万甚至更大，也不会因为数组越界而崩溃。
选择unordered_set而不是vector做危险邻居列表，主要理由是后续判断“某个邻居是否在箱子集合里”时，哈希查找是 O(1)；即使只是为了遍历邻居列表，vector 也完全够用。不过我的个人习惯是直接用unordered_set，因为如果题目数据里出现了重复配对，天然可以去重，避免同一个危险关系被反复写入浪费空间和时间。
存储部分的核心代码很短，但两个方向一定都要写：
forbid[a].insert(b); forbid[b].insert(a);2.3 箱子内部用集合判重，避免 O(K^2)
处理每个箱子时，先把 K 个货物编号都放入一个unordered_set<int> box，同时把它们按原顺序存入一个数组或者 vector 中，因为集合本身适合查找而不适合顺序遍历。这之后做两层检查：外层遍历箱子里的每个货物 x，内层遍历 x 的所有危险邻居 y，判断 y 是否存在于 box 集合中。如果存在就说明箱子里同时出现了 x 和 y，这对组合恰好是危险配对，箱子不安全。
这种做法把原先两两组合判断的 O(K^2) 压缩成了 O(K + 危险邻居遍历总长度)。绝大多数货物实际上只出现在少数几条危险配对里，邻居列表都很短，所以整体耗时一下子就降下来了。对比起来，这就是“给每个点开一张邻居表，再拿一个集合去查交点”的经典图模型操作。
3. 可提交的完整代码：C++ 主推版和 Python 应急版
3.1 C++ 完整代码：用 unordered_map + unordered_set
这里给出我最终提交用的 C++ 写法。代码里直接用了scanf和puts，主要是为了输入输出效率。cin不解除绑定同步时，在数据量较大场景下容易超时，这一点后面复盘时会重点说。
#include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); unordered_map<int, unordered_set<int>> forbid; for (int i = 0; i < n; i++) { int a, b; scanf("%d%d", &a, &b); forbid[a].insert(b); forbid[b].insert(a); } while (m--) { int k; scanf("%d", &k); vector<int> items(k); unordered_set<int> box; for (int i = 0; i < k; i++) { scanf("%d", &items[i]); box.insert(items[i]); } bool ok = true; for (int x : items) { // 如果 x 没有出现在任何危险配对中，直接跳过 if (!forbid.count(x)) continue; for (int y : forbid[x]) { // 在箱子里发现了 x 的危险邻居，判 No if (box.count(y)) { ok = false; break; } } if (!ok) break; } puts(ok ? "Yes" : "No"); } return 0; }这段代码有几个细节值得解释一下。
第一，forbid.count(x)用来判断这个货物是不是在某条危险关系里出现过。如果它压根不在危险关系表中，forbid[x]这个键不存在，直接跳过内层循环，避免了对空集合的无效遍历。第二，box.count(y)就是判断 y 是否在当前箱子里，哈希集合均摊 O(1)。第三，一旦发现冲突就立刻 break，不要在危险邻居列表里继续空跑，也不要把箱子里剩余货物继续判断。
3.2 Python 完整代码：笔试现场的快速实现
如果是在以 Python 作为主力语言的场景下，快速实现可以写成下面这样。关键在于用sys.stdin.buffer.read().split()一次性把所有数据读出来，而不是反复调用input()，后者在大数据量时会慢到让人怀疑人生。
import sys def main(): data = sys.stdin.buffer.read().split() idx = 0 n = int(data[idx]); idx += 1 m = int(data[idx]); idx += 1 forbid = {} for _ in range(n): a = int(data[idx]); b = int(data[idx + 1]); idx += 2 forbid.setdefault(a, set()).add(b) forbid.setdefault(b, set()).add(a) out = [] for _ in range(m): k = int(data[idx]); idx += 1 items = list(map(int, data[idx:idx + k])) idx += k box = set(items) ok = True for x in items: if x not in forbid: continue for y in forbid[x]: if y in box: ok = False break if not ok: break out.append("Yes" if ok else "No") sys.stdout.write("\n".join(out)) if __name__ == "__main__": main()setdefault(a, set()).add(b)的意思是：如果a这个键不存在，就先用一个空集合替代，然后往里面加 b。同理处理 b 的反向关系。这套写法比较紧凑，笔试时不占大脑缓存。
3.3 两版复杂度对照：为什么这样写不会超时
先看构建阶段，N 条危险配对，每条配对做两次集合插入，总开销 O(N)。检查阶段，每个箱子读入 K 个货物，建 box 集合 O(K)，然后遍历里面每个货物的危险邻居列表。平均情况下每个货物的邻居数量不多，所以一个箱子整体是 O(K + 危险邻居遍历总长度)。如果某个货物特别“热闹”，跟很多货物都不兼容，它确实会成为热点，但在 PAT 的数据范围内这种邻居列表再长也就万级，而且哈希查找均摊为 O(1)，依然可控。
相比之下，暴力两两检查每个箱子要 O(K^2)，箱子一多必然出事。换句话说，这道题的核心优化不是用什么高级算法，而是把一个“两两比较”的问题转换成了“查邻居列表是否命中集合”的问题，复杂度直接从平方掉到线性级别。
4. 复盘：我在这题上交过学费的三个位置
4.1 只存单向关系，箱子排序一变结果就变
这是我最开始踩的坑。写建表代码时只写了forbid[a].insert(b)，漏掉了反向。当时觉得“反正箱子里的货物我都会遍历到，只要遍历到 a 的时候能把 b 查出来就行了”。问题是，如果你恰好先遍历到 b，而 b 的危险邻居里没有 a，那这个箱子就被误判成了安全。这等于说“这个箱子是否安全”取决于箱子里货物出现的先后顺序，而题目显然不关心顺序。定位这个坑的方法也很简单：把 forbid 表完整打印出来，看看是不是每条关系都出现了两次，重点检查首尾两个方向是否都在。
4.2 箱子标记数组忘记重置，导致上一箱的货物残留
用全局数组标记“箱内出现过哪些编号”其实是常见做法，但每次处理完一个箱子后，你必须把所有标记过的位置重新设回 false。我刚开始写时觉得“把标记数组整体 memset 一遍不就完了”，结果某些数据量大的测试里，memset 的耗时也不小，更尴尬的是如果箱子里物品很多，而你只处理出现过的编号，忘记把其中某个编号恢复原状，就会污染下一个箱子。
后来我干脆放弃全局数组方案，改用为每个箱子单独建立一个局部unordered_set<int> box。这样不需要任何手动清理，局部变量生命周期结束自然释放，也不存在状态残留问题。这个教训给我的启发是：能不用全局可变状态的地方，尽量别用；尤其是做题时，局部集合带来的安全感比那一点内存开销值钱得多。
4.3 输入输出方式的效率坑
这道题虽然不算输入量最大的题，但 M 个箱子、每个箱子 K 个编号，累积起来也相当可观。C++ 里如果直接cin >> a >> b而不加ios::sync_with_stdio(false); cin.tie(0);，评测时真的可能被卡掉一点时间。Python 里每行调一次input().split()也远没有一次sys.stdin.buffer.read().split()快。输出方面，C++ 用puts或者把答案累积到一个字符串里最后统一输出，Python 把每个答案 append 到列表，最后"\n".join(out)，都比频繁刷缓冲要稳妥。
提示：如果你本地测试怎么都对，提交却偶尔判超时，优先检查是不是输入输出方式太“重”了。评测环境对 IO 的要求比本地环境严格得多。
5. 边界数据复盘：自己先当评测机
5.1 三组手工测试，先跑通再提交
第一组：一对危险关系直接出现在箱子里。
1 2 2 1 2这个箱子包含了配对1 2，而且两个编号都在，输出必须是 No。注意箱子里的两个编号顺序是1 2，正常遍历到 1 时就能发现 2 在集合中。这组数据主要验证基本判断逻辑。
第二组：没有任何危险配对。输入第一行是0 2，说明有 0 条危险配对、2 个箱子。
0 2 2 100 200 3 100 200 300所有箱子都应输出 Yes。这里看你的代码能否正确处理 N 为 0 的情况。理论上 while 循环一次都不进就行，但如果某个人的代码里用了特殊方式初始化 forbid，None 和空 dict 的区别要小心。
第三组：一个货物身处多个配对之中，也就是大度数中心。
3 1 1 2 1 3 1 4 3 1 2 3箱子中有编号 1、2、3。1 和 2 是危险配对，也同时是危险配对，所以输出 No。这种数据用来验证“一个货物有多个危险邻居”时不会漏判，也不会因为中间 break 而错过其他检查。
5.2 几个隐蔽测试点，考场上容易翻车
第一个隐藏点：箱子里出现重复编号。比如某个箱子是2 100 100，虽然 K 显示 2，但两个货物编号一样。题目从来没有保证箱内编号互不相同，如果你用数组标记的方法并且只是简单计数，重复编号不会导致误判，但如果你把“箱子中该编号出现两次”理解成“该编号和自身形成了两件货物”，逻辑上要小心，因为只有不同编号之间的关系才起作用。用集合处理时天然去重，反而是最安全的。
第二个隐藏点：货物编号没有出现在任何危险配对中。这种编号在 forbid 表里不存在，遍历时必须直接跳过。代码里if (!forbid.count(x)) continue;就是为这种情况准备的。
第三个隐藏点：危险配对的编号顺序和箱子里的顺序不一致。例如危险配对是5 10，箱子是[10, 5]。正确解法里先遍历 10，10 的邻居里有 5，而 5 也在 box 集合，也能正确判 No。如果你使用全局数组但只写了单向关系，这里就会翻车。
第四个隐藏点：大量输出时，最后一个输出后面不要误加多余空格或者多余换行。PAT 这类评测对空行并不严格，但如果你用printf("No\n")就固定了格式，不要再去补一个额外空格。
6. 那根偶然被点通的线：这题的图论本质
6.1 把危险配对看成无向图的边
做这题做到第三遍时，我突然意识到它其实是一个“无向图存在性查询”问题。把每个危险品编号看成图上的点，一条危险配对看成两点之间的一条无向边。于是题目变成：给定一个点集（箱子里的货物），判断这个点集里存不存在一条边，即是否存在两个点之间有直连边。
这其实就是判断“诱导点集是不是一个独立集”的子任务。我们不需要求出最大独立集，也不需要去遍历图上的所有点，只需要判断一个很小的点集内部有没有边而已。所以最合适的数据结构就是邻接表加集合：邻接表用来表达点的邻居关系，集合用来表达当前点集的成员。两者合在一起，判断点集内部有没有边就是遍历每个点看它邻居是否也在这个点集里。
6.2 两个可以被复用的刷题套路
第一，凡是遇到“某些东西不能共存”的题，先建冲突邻接表，不要急着两层循环去暴力枚举所有组合。这套模式在乙级里并非 1090 独有，在很多模拟题、集合判断题里都会反复出现。
第二，如果某个查询只需要判断一个子集内部是否满足某类关系，先把这个子集放进哈希集合，再反向查每个元素的扩展信息，往往能省下 O(K^2) 的时间。这个“集合 + 邻接表”的组合会比直接维护二维关系矩阵更加灵活，尤其当编号范围不固定时，几乎是唯一不依赖数据范围的通用写法。
最后说个我自己的调试习惯。写这类题时，我先不在编译器里边改边试，而是把 forbid 表和每个 box 的集合打印出来，人工核对两三组数据。别嫌这一步麻烦，它能让我在提交之前就看出很多逻辑错误。还有一个在考场上不能调试时特别好用的小技巧：自己脑内构造最小用例，就是一对危险配对、箱子顺序颠倒、以及一箱只有一件货物。这三种极端数据全过，代码基本就稳了。1090 这道题并不难，但它让我把“哈希表建邻接表 + 集合判重”这一套用得特别熟练，后面遇到不少模拟题也都沿着这套思路去写，省了很多试错成本。
