关于算法-数据结构:PAT甲级1149-Dangerous-Goods-Packaging

题目粗心：

现有 N 对互不兼容的物品清单和 M 个须要装箱的货物清单，询问每一个须要装箱的货物清单是否能够齐全兼容并装箱，如果能够输入 Yes，否则输入 No。

算法思路：

首先应用 $incompatible$ 二维数组存储每一个物体的所有不兼容的物体，并应用 $incompat$ 数组记录以后货箱有哪些无奈兼容的物品 (为 true 即为不可兼容)，而后在每一个须要装箱的货物进行顺次装箱的时候，先查看以后物品是否与曾经装箱的物品兼容，如果是，那么就将与该物品不兼容的所有物品的 $incompat$ 记录为 true，只有在装箱的时候呈现一次 $incompat$ 为 true 的状况，就阐明该货物清单无奈齐全装箱，并应用 $isCompatible$ 记录为 false, 否则为 true, 最初依据 $isCompatible$ 进行输入 Yes 和 No 即可。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

vector<int> incompatible[100000];// 每一个物品的所有不兼容的物体汇合
bool incompat[100000];// 以后集装箱不可兼容的物体

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    int a,b;
    for (int i = 0; i < N; ++i) {
        // N 对互不兼容的物品
        scanf("%d %d",&a,&b);
        incompatible[a].push_back(b);
        incompatible[b].push_back(a);
    }
    for (int i = 0; i < M; ++i) {
        int num;
        scanf("%d",&num);
        memset(incompat,0, sizeof(incompat));
        bool isCompatible = true;// 以后集装箱是否能够兼容所有物品
        for (int j = 0; j < num; ++j) {
            int index;
            scanf("%d",&index);
            if(!incompat[index]){
                // 将 index 退出其中，并且将其不兼容的物品全副设置为 true
                for(auto &item:incompatible[index]){incompat[item] = true;
                }
            } else {isCompatible = false;// 这里不能 break, 因为得承受所有的输出数据}
        }
        if(isCompatible){printf("Yes\n");
        } else {printf("No\n");
        }
    }
    return 0;
}