PAT1149 Dangerous Goods Packaging

原题

题目大意及思路

不相容的物品放在同一个容器中会引起爆炸。
输入数据中给了两个模块：
第一块是不相容物品对
第二块是m个inquiries，若其中不存在不相容物品对则输出yes，否则输出no

首先对于不相容物品对信息的存储，我们不选取邻接矩阵，因为题中每一个物品的编号都是一个五位数，若想全部存储的话，需要一个100000*100000的矩阵，这个会太大造成报错。同样地，我们也不选取邻接表，因为所用的存储空间也比较浪费，所以在这里我们选取map与vector的复合结构：map<int,vector<int>> mv;这样能够在给出的不兼容物品对不多的情况下减少内存浪费。
另外一个比较重要的点在于每次容器内物品的检查，刚开始我采用的是vector存储一个容器里的物品编号，用map<int,set<int>> ms 中find（）函数来查看是否有对应元素，但find（）函数的时间复杂度比较高，所以后几个测试样例没有通过。
在参考其他大神的代码后，他们采用a[100000]来存储每一个inquiry中现存的编号，在遍历该编号的邻接矩阵时就不需要用find函数而是用一个时间复杂度为a[mv[data[i]][j]]的判断语句来代替。

代码

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
map<int,vector<int>> mv;
int main(){int n,m;cin>>n>>m;while(n--){int i,j;cin>>i>>j;mv[i].push_back(j);mv[j].push_back(i);}while(m--){int k;cin>>k;int a[100000]={0};bool flag=true;vector<int> data(k);for(int i=0;i<k;i++){cin>>data[i];a[data[i]]=1;}for(int i=0;i<k;i++){if(flag==false) break; for(int j=0;j<mv[data[i]].size();j++){if(a[mv[data[i]][j]]) flag=false;}}printf("%s\n",flag==true?"Yes":"No");}
}

运行截图

收获

stl库中的函数固然简易好用，但要算上它们的时间复杂度，考虑是否有其他时间复杂度更低的语句来代替。