PAT_A1149#Dangerous Goods Packaging

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

• 散列（Hash）

Attention:

• 若1个元素与N个元素互斥，属于散列；若一系列元素相互排斥的话，则是并查集

Code:

 /*

 Data: 2019-08-04 16:38:35

 Problem: PAT_A1149#Dangerous Goods Packaging

 AC: 32:04

 题目大意：

 题目大意：

 给一份两两互斥的清单，再给出货品清单，判断该批货品是否兼容

 基本思路：

 二维数组存储各个物品的互斥集，

 设置该批物品存在位=1，遍历该批物品的互斥集；

 若互斥集中物品的存在位=1，则不兼容

 */

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int M=1e6;

 vector<int> st[M];

 int exist[M],goods[M];

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     int n,m,k,v1,v2;

     scanf("%d%d", &n,&m);

     for(int i=; i<n; i++)

     {

         scanf("%d%d", &v1,&v2);

         st[v1].push_back(v2);

         st[v2].push_back(v1);

     }

     while(m--)

     {

         scanf("%d", &k);

         fill(exist,exist+M,);

         for(int i=; i<k; i++)

         {

             scanf("%d", &goods[i]);

             exist[goods[i]]=;

         }

         for(int i=; i<k; i++)

             for(int j=; j<st[goods[i]].size(); j++)

                 if(exist[st[goods[i]][j]]==){

                     k=;break;

                 }

         if(k)   printf("Yes\n");

         else    printf("No\n");

     }

     return ;

 }