题目背景与样例说明

本题的输入分两部分，第一部分是会发生冲突的物品对，第二部分是需要装箱的物品列表。你需要判断需要装箱的同一批物品中是否存在互相冲突的物品。

Sample Input

6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333

Sample Output

No // 20004 和 20003 冲突
Yes
Yes

代码

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n, m, x, y, cnt;
    vector<int> book[100000]; // 这里类似于图的邻接表，book[i](vector 类型) 存储所有与 i 物品冲突的物品编号
    int a[1010];
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &x, &y);
        book[x].push_back(y);
        book[y].push_back(x);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &cnt);
        bool flag = true; // 是否存在冲突
        for (int j = 0; j < cnt; j++) scanf("%d", &a[j]);
        for (int j = 0; j < cnt; j++) {
            for (int k = j + 1; k < cnt; k++) { // 判断 a[j] 和 a[k] 是否存在冲突
                for (int p = 0; p < book[a[j]].size(); p++) {
                    if (book[a[j]][p] == a[k]) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) break;
            }
            if (!flag) break;
        }
        if (flag) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}