这一题是hash题目。题目本身不难,但是有地方要注意,一件物品可能与多个物品不兼容,这与以前夫妇双方在场问题是不一样的。
算法步骤:
声明vector类型数组和布尔类型hash数组将输入数据存到vector数组中将输入进来的一组id存到临时数组中循环判断是否有两件不兼容的物品同时存在输出判断结果
关键点:
存储两件不兼容物品的信息不是像常规方法采用int数组,而是采用vector数组。
核心代码:
for (int i = 0; i < n;i++){int temp1, temp2;scanf("%d %d", &temp1, &temp2);incompatible[temp1].push_back(temp2) ;incompatible[temp2].push_back(temp1) ;}
代码如下:
#include<iostream>#include