PAT乙级1090这道题，在乙级题库里属于那种“看着简单，但第一次动手很容易翻车”的典型题目。它表面上是模拟一个装箱检查流程，实际上考的是多对多关系应该怎么存、怎么查，以及你处理输入细节够不够仔细。很多人在刷题时一看题目觉得稳了，结果提交上去好几个测试点红成一片，问题几乎都出在数据结构选型和边界处理上。
这道题非常适合正在准备PAT乙级的同学练手，也适合那些刚开始接触哈希表、关联容器，想通过一道具体题目理解“映射关系”该怎么用的朋友。题目本身不涉及复杂算法，但能把C++里STL的基础容器用法、图论里邻接表的思想、以及“先用集合收齐再集中比对”这类编程习惯都串起来。把这题吃透，后面的关系类题目你会觉得顺很多。
1. 题目到底在说什么
1.1 核心需求解析
题目的场景是危险品运输。有些物品天生犯冲，不能放在同一个箱子里，比如氧化剂和易燃物必须分开。输入会先给出若干对这样的“互斥物品对”，然后给出若干个箱子，每个箱子有一张物品清单，你需要逐一判断这张清单里是否存在任意一对互斥物品同时出现。如果存在，就输出“No”，表示这箱不安全；如果不存在，就输出“Yes”。
光看描述这确实是个纯模拟题，似乎只要把每个箱子的物品列出来，两两比对有没有互斥对就行。但问题就出在“怎么比对”上。输入给出的互斥关系是分散的，箱子里的物品也是分散的，如果每次判断都临时去原始关系里翻一遍，性能压力会很大，而且代码写起来会非常别扭。
我举个自己构造的最小样例来演示一下判断逻辑。假设输入是：
2 2 10001 10002 10003 10004 3 10001 10002 10003 2 10005 10001第一行表示有2对互斥关系、2个箱子。互斥对是(10001, 10002)和(10003, 10004)。第一个箱子有3件物品：10001、10002、10003，其中10001和10002正好是互斥对，所以这个箱子输出No。第二个箱子有2件物品：10005和10001，这两件之间没有互斥关系，所以输出Yes。
1.2 表面是模拟，实质考什么
这条题目的考点非常集中，一共有四个层次。第一层是哈希容器的运用，你需要一个能快速查询“某物品是否在箱子中”的数据结构。第二层是图论里邻接表的思想，互斥关系本质上是一堆无向边，你不能把它们铺成一张稀疏大矩阵，而是要把每一条边都挂到对应的点上。第三层是双向关系的处理，一对互斥物品，两边的存储都要做，只存一边就会漏判。第四层才是大多数新手翻车的地方，也就是编号的读入方式，前导零、字符串与整数的差别，细枝末节却直接影响结果。
这四个层次难度都不高，但合在一起就变成了一道非常综合的基础题。我甚至觉得，这道题就是专门用来考察“基础功底扎不扎实”的：你会不会用映射来组织不确定长度的关系列表，有没有养成“先完整读入再统一判断”的习惯，能不能在最短时间内选出正确的存储结构。这些能力在乙级后半段乃至甲级入门时都特别重要。
2. 从暴力到哈希：解题思路的推演
2.1 第一反应：二维数组为什么不行
看到这种“两两配对”的关系题，很多人的第一反应是开一个二维布尔数组，比如g[a][b]表示物品a和物品b互斥。可惜这个方案在这题里基本是死路一条。题目里的物品编号是五位数字，范围最大能到00000到99999，足足有十万个不同的编号。如果你开一个100000乘100000的bool数组，算一下就会发现需要100亿个字节，换算过来接近10GB。判题机的内存限制通常只有256MB，这差了四十多倍，连编译阶段都可能直接把进程干崩溃。
就算你用vector<vector >这种压缩存储的写法，每个bool只占一位，内存也还要1.25GB左右，依然超出限制。真正的问题在于，二维矩阵把“所有物品之间有没有关系”这个全集都存了下来，但实际有关系的位置极少。互斥关系最多只有N对，N是输入给出的，相比十万乘十万的全部组合数量，稀疏得不能再稀疏。学过图论的同学应该意识到了，稀疏关系就该用稀疏的方式存储，也就是邻接表。
这里打个生活化的比方。你要知道全班谁和谁有仇，与其画一张巨大的座位表，每个格子都标上关系，不如每个同学手里拿一张“仇人名单”，名单上只有确实犯冲的人。这样既省纸又省时间。互斥关系表就是这张名单。
2.2 邻接表思路：每个物品挂一份禁忌清单
既然不能用矩阵，那我们自然想到给每个物品维护一个动态数组，里面存放所有和它互斥的物品编号。C++里最自然的做法就是用unordered_map<int, vector >，key是物品编号，value是这个物品的禁忌清单。每读入一对互斥关系(a, b)，就执行两次操作：在a的清单里加入b，在b的清单里加入a。
这个“双向添加”是整道题最容易出错的点，我后面会专门讲。你先记住一个原则：互斥关系是无向的，如果a不能和b同箱，那么b也绝对不能和a同箱。所以从a的角度看，b是禁忌；从b的角度看，a同样是禁忌。只存一个方向，相当于让其中一个物品失忆了。
有了这份清单以后，检查箱子就变得很简单。先把箱子里的所有物品放进一个哈希集合，然后遍历箱子里的每一个物品x，再遍历x的禁忌清单里的每一个物品y，如果y恰好也在这个箱子的哈希集合里，那就说明出现了互斥物品同箱的情况，直接判为不安全。
2.3 为什么选哈希容器而不是其他结构
你可能会有疑问：为啥非要用unordered_map和unordered_set，用map和set不行吗？当然行，map和set也完全能解出这题。区别在于底层实现。map和set是有序的红黑树，插入和查询都是O(log n)；unordered_map和unordered_set底层是哈希表，平均情况下的插入和查询是O(1)。在数据量较大的时候，哈希版本会明显更快，再加上这题的关键操作就是频繁查询“某个物品在不在集合里”，用哈希表是最贴需求的。
还有一个可选的优化写法。既然题目明确编号是五位数字，那么编号范围就是确定的0到99999，在这种情况下，你甚至可以直接开一个vector ban[100000]这样的静态数组，让数组下标直接当物品编号用。这样省去了哈希函数计算，速度是最快的。不过这写法通用性差一点，一旦题目把编号范围改得很大，比如10的18次方，静态数组就无能为力了。我个人建议先把unordered_map版本写熟练，理解了通用思路之后，再去了解数组下标版本作为加速技巧。
3. 完整实现与关键细节
3.1 读入建表这一步到底在做什么
建表代码看起来很短，但每个细节都有讲究。核心代码是这两行：
ban[a].push_back(b); ban[b].push_back(a);这里用到了unordered_map的operator[]特性：当你用下标访问一个不存在的key时，它会自动创建一个空的vector，然后你再往里push_back。这让我们不用先判断key是否存在，写起来非常省心。不过前提是你确定这个map后面会大量使用，否则频繁创建空vector会有点浪费，但在这题的规模下，直接用没问题。
读入时要注意检查返回值和输入结束的问题。用scanf读整数时，如果返回值不是期望的数量，直接结束程序是比较稳妥的写法。不过更重要的是时刻记住，我们要存双向。为了加深印象，我会在4.1节用一个错误版本对比，现在先记住这个原则。
3.2 核心判定逻辑：先收齐再逐项比对
每读入一个箱子，不要急着判断。为什么？因为你判断的条件是“箱子里的另一个物品是否在禁忌清单上”，这个查询依赖一个完整的信息前提：你得先知道这个箱子到底装了什么。如果边读边判，读到第一个物品时，你根本不知道后面还会不会出现它的禁忌物品，逻辑非常容易乱。
正确的做法是分两步走。第一步，把这一箱的所有物品读入一个普通vector，同时插入一个unordered_set，用set来代表“这箱里有哪些物品”。第二步，遍历vector里的每个物品x，然后遍历ban[x]里的每个物品y，用box.count(y)判断y是否在箱子中。只要有一次命中，就说明箱子不安全。
这一步其实隐含了一个常见的算法习惯：先完整收集数据，再基于完整数据集进行推理。很多新手在模拟题上翻车，不是不会写逻辑，而是数据还没读全就开始处理，结果一边读一边丢上下文。养成“先收齐，再处理”的习惯，对很多题目都有帮助。
3.3 完整代码与逐行注释
下面给出完整的C++实现。这段代码可以直接提交运行，我尽量在注释里解释每一步的意图。
#include <cstdio> #include <unordered_map> #include <unordered_set> #include <vector> int main() { int n, m; // 第一行：n对互斥关系，m个箱子 if (scanf("%d %d", &n, &m) != 2) { return 0; } // ban[x] 存储所有与x互斥的物品编号 std::unordered_map<int, std::vector<int>> ban; for (int i = 0; i < n; ++i) { int a, b; scanf("%d %d", &a, &b); // 互斥是双向的，两个方向都要登记 ban[a].push_back(b); ban[b].push_back(a); } for (int i = 0; i < m; ++i) { int k; scanf("%d", &k); // 当前箱子的物品数量 std::vector<int> items; // 按读入顺序保存物品 std::unordered_set<int> box; // 用于快速查询某个物品是否在箱内 items.reserve(k); for (int j = 0; j < k; ++j) { int x; scanf("%d", &x); items.push_back(x); box.insert(x); } bool safe = true; for (int x : items) { for (int y : ban[x]) { if (box.count(y)) { safe = false; break; } } if (!safe) { break; } } puts(safe ? "Yes" : "No"); } return 0; }这段代码的时间复杂度是这样：建表阶段是O(N)，每个箱子阶段，假设箱内有K个物品，每个物品的禁忌清单平均长度为L，那么单箱最坏情况是O(KL)。从整体来看，这样处理足够快。空间上，禁忌表总共存了2N个关系，箱子的集合只在一箱的范围内使用，内存占用非常小。
再补一个数组优化版本，如果你确定编号范围局限在0到99999，可以这样写：
#include <cstdio> #include <vector> #include <unordered_set> std::vector<int> ban[100000]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { int a, b; scanf("%d %d", &a, &b); ban[a].push_back(b); ban[b].push_back(a); } for (int i = 0; i < m; ++i) { int k; scanf("%d", &k); std::unordered_set<int> box; std::vector<int> items; for (int j = 0; j < k; ++j) { int x; scanf("%d", &x); items.push_back(x); box.insert(x); } bool safe = true; for (int x : items) { for (int y : ban[x]) { if (box.count(y)) { safe = false; break; } } if (!safe) break; } puts(safe ? "Yes" : "No"); } return 0; }这个版本去掉了unordered_map的哈希计算开销，写起来也更简单。如果你在考场时间紧张，这是优先选择。但面试或练习时，我更推荐前一个通用版本，因为它的思路可以迁移到更多场景。
4. 我踩过的坑与排查实录
4.1 只存单向配对造成的漏判
这个坑我猜至少一半的人踩过。当时我写第一版代码时，脑子里想的是“读入a和b，就在a的记录里挂上b”，顺手就只写了ban[a].push_back(b)这一行。自以为关系已经存好了，结果一测，某些箱子明明包含互斥对，却输出了Yes。
原因很简单：如果只在a的禁忌表里存了b，那么当箱子里的物品遍历顺序是先遇到b再遇到a时，程序会先查b的禁忌表，但b的禁忌表是空的，于是直接跳过，后面即使再遇到a，也不会重新检查b了。互斥关系是双向的，你让一边“失忆”，另一边再努力也没用。后来我在代码里加上了ban[b].push_back(a)，所有测试点立刻通过。
4.2 编号前导零：字符串和整数的抉择
我最初看题时注意到编号是五位数字，心想这不就用字符串处理吗，于是把编号都读成string。结果掉进了另一个大坑。编号00001和1，在字符串层面上是两个不同的值，但它们在语义上指的是同一个物品。比如一个互斥对是(00001, 00002)，箱子清单里写的是(1, 2)，用字符串一比较，1不等于00001，2不等于00002，原本应该判为不安全的箱子，被误判成了安全。
用int读就没有这个问题。scanf读整数时会把前导零自动去掉，00001直接变成1，与清单里的1完全一致。所以在这道题里，编号一律用int读最省心。如果你非要坚持用字符串，也必须统一格式，比如都按五位补齐之后再比较，那样代码会麻烦很多，完全没有必要。
4.3 二维数组内存爆炸的现场记录
第一次提交爆内存的时候，我是真的懵了。当时想着关系检查最方便就是二维矩阵，于是直接写了个100000乘100000的bool矩阵，结果编译倒是过了，运行一秒钟内内存直接爆炸。后来算了一下，100亿字节，哪怕1字节的bool，都要10GB，而判题机一般限制256MB。这一课让我彻底改掉了“见关系就开矩阵”的惯性思维。从那以后，我遇到稀疏关系第一反应一定是邻接表。这种关系到底有多稀疏呢，输入给出的互斥对哪怕有一万对，也才两万条边，和十亿级别的矩阵相比微不足道。
4.4 常见问题速查表
| 症状 | 可能原因 | 解决办法 |
|---|---|---|
| 明明有互斥对却输出Yes | 只存了单向互斥关系 | 在a和b的清单里都登记对方 |
| 有冲突但总是漏判 | 边读边判断，查询时箱子集合不完整 | 先完整读入本箱所有物品，再集中检测 |
| 前导零编号导致误判 | 用字符串读编号且未统一前导零 | 统一用int读入，让00001自动变成1 |
| 内存超限 | 用二维矩阵存互斥关系 | 改用邻接表，unordered_map加vector |
| 运行超时 | 每箱物品两两暴力比对 | 把箱内物品放入哈希集合，再用禁忌表查 |
还有一个小问题值得提一下：有的同学在遍历箱子时，把判断逻辑写成了在双重循环里同时查a和b，也就是说先判断(a, b)，再对称判断(b, a)，这时如果禁忌表存的是双向的，就会重复判断，虽然不影响输出结果，但增加了不必要的计算量。正确做法是只从一个方向遍历禁忌表，因为双向已经保证每个互斥对都会被查到一次。
5. 从1090延伸开：这类冲突检测题的通用解法
5.1 你已经掌握了一个可复用的模式
刷完这题，要有一类题的通法意识。先说模式识别的特征：第一，输入会给你若干二元冲突关系，比如“a不能和b同时出现”；第二，查询过程会给出一组元素，问你“这组元素里是否存在冲突”。只要看到这两个特征，你基本可以直接套用1090的思路：用邻接表存冲突关系，把待检测元素放进哈希集合，然后遍历每个元素和它的冲突列表，看冲突目标是否在集合中。
这个模式在不少题目里都能用。比如判断一排课程安排里有没有时间冲突，判断一组文件依赖里有没有循环引用，都很相似。循环引用那个要复杂一些，因为它还涉及DFS或拓扑排序，但基础的关系存储逻辑是一样的。1090相当于是这个模式的最小可运行版本，把哈希表、集合、邻接表这三个概念全练了一遍。
5.2 一套可以直接套用的模板
下面这个模板几乎可以直接复用：
// 1. 建立冲突表 for (每个冲突对 a b) { ban[a].push_back(b); ban[b].push_back(a); } // 2. 对每个待检测组合 for (每个组合) { // 2.1 收集组合元素到哈希集合 std::unordered_set<int> s; for (组合里的元素 x) { s.insert(x); } // 2.2 逐一检查冲突 bool ok = true; for (组合里的元素 x) { for (int y : ban[x]) { if (s.count(y)) { ok = false; break; } } if (!ok) break; } print(ok ? "Yes" : "No"); }模板本身不重要，重要的是你明白每一步在解决什么问题。“建立冲突表”是在做关系存储，“收集到哈希集合”是在为O(1)查询做准备，“逐一检查冲突”是在利用存储结构缩小搜索范围。想明白这三个环节，应对同类题目就很从容了。
5.3 一点备考的真实体会
针对PAT乙级这个区间段的题目，我个人的体会是：大部分题根本不考高深算法，核心就看你基础数据结构用得好不好。1090这道题的难度，恰恰卡在一个特别微妙的点：它不要求你发明什么新方法，只要求你用最合适的数据结构，把一句大白话翻译成代码。“物品与物品之间存在互斥关系，判断一个集合内部是否含有互斥对”，这句话本身连算法都算不上，但能一次写对的人，说明STL基本功和细节意识都到位了。
我还建议你刷完1090以后，自己做个变体练习。把“两个物品互斥”改成“三个物品一组互斥，必须三个同时出现才算是冲突”，看一下代码要调整哪些地方。再或者，不满足于只输出Yes或No，而是要求输出具体是哪一对物品冲突了，代码又要怎么改。这两个变体都不难，但能帮你把哈希表和集合的用法记得更牢。
最后再说一个经常被忽略的技巧：在笔试环境里，如果你发现自己写代码时不断在想“这个容器到底选哪个”，那大概率说明这个题考的就是容器的取舍。1090就是一个典型。把unordered_map、unordered_set、vector这三者之间的关系理顺，这道题的得分就是板上钉钉的事。这题别看分值不算高，对我后来刷更复杂的哈希相关题目帮助特别大，希望你也能从中找到那种“思路通了”的感觉。
