PAT A1149 Dangerous Goods Packaging (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
/* 题意： 危险的物品混合，给出n对不能混合在一起的物品id，进行m 次询问，每次询问列出k项物品id，若k个物品里面包含任意一对不能 混合的物品id，则输出No，否则输出Yes 思路：因为每个物品不能混合的物品可能有很多，因此可以考虑 使用map来存储每个物品不能与之混合的所有物品id。在判断给出的k件货物是否是相容的时候， 判断任一货物的不兼容货物是否在这堆货物中 。 */
const int maxId=1e6+10; 
map<int,vector<int>> mp;
int main(){
	int n,m,k;
	cin>>n>>m;
	for(int i=0,a,b;i<n;i++){
		cin>>a>>b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	while(m--){
		bool inList[maxId];
		fill(inList,inList+maxId,false);
		cin>>k;
		vector<int> v(k);
		for(int i=0;i<k;i++){
			cin>>v[i];
			inList[v[i]]=true;//id为v[i]的物品在物品序列中 
		}
		bool flag=false;//flag==false表示能够混合 
		for(int i=0;i<k;i++){
			int len=mp[v[i]].size();
			for(int j=0;j<len;j++){
				if(inList[mp[v[i]][j]])flag=true;
			}
		}
		printf("%s\n",flag?"No":"Yes");
	}
	
	
	return 0;
}