PAT A1149 Dangerous Goods Packaging
和单身狗那道题类似，不同的是，这里的狗都可以脚踏N只船（我最开始都没注意到，，）所以首先多对多关系存入二维数组，然后维护一个标记数组，对于每一个输入的点，标记其出现了，并且遍历这个点的邻接点，看有没有之前出现过的，if有，则爆炸#include<iostream>#include<vector>using namespace std;vector<vector<int> > pair_(100000);vector<bool> shot(100000);int main(){int M,K;cin >> M >> K;for(int i = 0;i < M;i ++){int a,b;cin >> a >> b;pair_[a].push_back(b);pair_[b].push_back(a);}for(int i = 0;i < K;i ++){for(int j = 0;j < shot.size();j ++) shot[j] = false;int n,tmp;cin >> n;bool flag = true;for(int j = 0;j < n;j ++){cin >> tmp;if(!flag) continue;shot[tmp] = true;for(int k = 0;k < pair_[tmp].size();k ++){if(shot[pair_[tmp][k]]){flag = false;break;} }}if(flag) cout << "Yes\n";else cout << "No\n";}return 0;}
