1149 Dangerous Goods Packaging
When shipping goods with containers, we have to be careful not to pack some incompatible goods into the same container, or we might get ourselves in serious trouble. For example, oxidizing agent （氧化剂） must not be packed with flammable liquid （易燃液体）, or it can cause explosion.
Now you are given a long list of incompatible goods, and several lists of goods to be shipped. You are supposed to tell if all the goods in a list can be packed into the same container.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: N (≤104), the number of pairs of incompatible goods, and M (≤100), the number of lists of goods to be shipped.
Then two blocks follow. The first block contains N pairs of incompatible goods, each pair occupies a line; and the second one contains M lists of goods to be shipped, each list occupies a line in the following format:
K G[1] G[2] ... G[K]
where K (≤1,000) is the number of goods and G[i]'s are the IDs of the goods. To make it simple, each good is represented by a 5-digit ID number. All the numbers in a line are separated by spaces.
Output Specification:
For each shipping list, print in a line Yes if there are no incompatible goods in the list, or No if not.
Sample Input:
6 3 20001 20002 20003 20004 20005 20006 20003 20001 20005 20004 20004 20006 4 00001 20004 00002 20003 5 98823 20002 20003 20006 10010 3 12345 67890 23333
Sample Output:
No Yes Yes
题意
题目首先给定哪些物品不相容，然后再判断给定的箱子中，每个物品之间是否都是相容的。
思路
具体思路如下：
1.先将将给定不相容的物品分别放入数组 a 和数组 b 。
2.将需要判断的箱子中的物品放入 unordered_set 容器中，方便后续查询。
3.从数组 a 和数组 b 中遍历每一对不相容的物品，如果发现有一对物品同时存在容器中，则该箱子不满足要求，反之该箱子是安全的。
4.最后，输出查询的结果。
代码
#include<bits/stdc++.h> using namespace std; const int N = 10010; int n, m, k; int a[N], b[N]; int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; while (m--) { //将该箱子中物品放入容器方便后续查询 cin >> k; unordered_set<int> s; for (int i = 0; i < k; i++) { int x; cin >> x; s.insert(x); } //判断该箱子中是否存在一对不容物 bool success = true; for (int i = 0; i < n; i++) if (s.count(a[i]) && s.count(b[i])) { success = false; break; } //输出查询答案 if (success) puts("Yes"); else puts("No"); } return 0; }
