PAT甲组1149 Dangerous Goods Packaging思路解析和代码

甲组1149 Dangerous Goods Packaging思路解析和代码"/>

PAT甲组1149 Dangerous Goods Packaging思路解析和代码

A1149

题目链接

个人思路

题意

给出一批货物，判断这批货物中是否都能共存

思路

用二维vector存储每个货物与其不能共存的物品，暴力遍历即可通过

注意

• 一种货物可能有多个不能共存的物品，因此不能单纯的使用map
• 1e6数据范围的二维vector也没有超限，看来vector的潜力很大

个人思路代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int N, M;
vector<int> v[maxn];
unordered_map<int, bool> vis;
int main(int argc, char *argv[]) {scanf("%d%d", &N, &M);for(int i = 0; i < N; ++i){int a, b;scanf("%d%d", &a, &b);v[a].push_back(b);}vector<int> goods;while(M--){int K;scanf("%d", &K);goods.clear();vis.clear();bool cmplt = true;for(int i = 0; i < K; ++i){int x;scanf("%d", &x);goods.push_back(x);vis[x] = true;}for(int i = 0; i < goods.size(); ++i){if(cmplt == false)break;int a = goods[i];if(v[a].size() == 0)continue;else{for(int j = 0; j < v[a].size(); ++j){int b = v[a][j];if(cmplt == false)break;if(vis[b] == true)cmplt = false;}}}if(cmplt == false)printf("No\n");elseprintf("Yes\n");}return 0;
}