集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。
本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。
输入第一行给出两个正整数：N (≤10 4 ) 是成对的不相容物品的对数；M (≤100) 是集装箱货品清单的单数。
随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：
K G[1] G[2] … G[K] 其中 K (≤1000) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。
对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。
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
No Yes Yes
分析最主要的是想一种数据结构 可以在k的数的队伍里方便的寻找是不是有冲突的1. 想怎么存储这些不相容的关系 可以使用map 两个不相容的关系互相加入为其值2. 光用map还不行，可能一个数有很多个不相容的关系，所以用map和set的结合（vector也行），set作为map的值，方便查找3. 我一开始用的查找方法是：队伍互相遍历一遍，看互相是不是在自己不相容的数里面 ，不过有个超时4. 我看到上有人：拿出队伍每个元素不相容的，看是不是在队伍里面后者快很多，应该是数据的问题 #include <iostream> #include <vector> #include <algorithm> #include <map> #include <set> using namespace std; int main() { int N, M; scanf("%d%d", &N, &M); map<int, set<int>> s; while (N--) { int x, y; scanf("%d%d", &x, &y); // 分别存放到对方的不相容关系里面 s[x].insert(y); s[y].insert(x); } int k; while (M--) { cin >> k; int f = 0; set<int> t; for (int i = 0; i < k; i++) { int x; scanf("%d", &x); t.insert(x); } // 遍历一遍队伍 for (auto e : t) { // 看当前队伍元素 的 不相容的数 for (auto x : s[e]) { // 如果在队伍里能找到不相容的 if (t.find(x) != t.end()) { f = 1; break; } } if (f) break; } if (f) { cout << "No\n"; } else cout << "Yes\n"; } return 0; }