训练　集合运算

题目描述（POJ2443）：给定N个集合，第i个集合Si有Ci个元素（集合可以包含两个相同的元素）。对集合中的每个元素都用1～10 000的整数表示，查询元素i和元素j是否同时属于至少一个集合。换句话说，确定是否存在一个数字k（1≤k≤N），使得元素i和元素j都属于Sk。

输入：第1行为一个整数N（1≤N≤1000），表示集合的数量。第2～N+1行，每行都以数字Ci（1≤Ci≤10 000）开始，后面有Ci个数字，表示该集合中的元素。第N+2行为一个数字Q（1≤Q≤200 000），表示查询次数。接下来的Q行，每行都为一对数字i和j（1≤i， j≤10 000，i可以等于j），表示待查询的元素。

输出：对于每次查询，若存在这样的数字k，则输出“Yes”，否则输出“No”。

题解：本题查询两个元素是否同时属于一个集合（至少一个），可以用位图解决。

输入样例1：

对每个元素都可以用一个二进制数记录所属的集合，最右侧为低位或0位。这里首先定义一个位图数组s［］，例如，1属于第1个集合，就将1对应的二进制数的第1位设置为1，即s［1］=0010；1还属于第2个集合，就将1对应的二进制数的第2位设置为1，即s［1］=0110，表示1属于第1、2个集合。同理，s［2］=0110，s［3］=0010，s［5］=0100，s［10］=1000。

1.算法设计

（1）定义一个位图数组，对每个元素都用二进制表示其所属的集合。

（2）根据输入的数据，将元素所属集合对应的二进制位设置为1。

（3）查询x、y是否同时属于一个集合，统计s［x］&s［y］的二进制数中1的数量，若大于或等于1，则输出“Yes”，否则输出“No”。

2.算法实现