一 问题描述

给定 N 个集合，第 i 个集合 Si 有 Ci 个元素（集合可以包含两个相同的元素）。集合中的每个元素都用 1~10000 的整数表示。查询给定的两个元素 i 和 j 是否同时属于至少一个集合。

输入：输入的第 1 行包含一个整数N，表示集合的数量，第 2 ~ N + 1 行，每行都以数字 Ci 开始，后面有 Ci 个数字，表示该集合中的元素。第 N + 2 行包含一个数字 Q，表示查询数。接下来的 Q行，每行都包含一对数字 i 和 j，表示待查询的元素。

输出：对于每个查询，如果存在这样的数字 k ，则输出 YES，否则输出 NO

输入样例：
3

3 1 2 3

3 1 2 5

1 10

4

1 3

1 5

3 5

1 10

输出

YES

YES

NO

NO

二 算法设计

本题查询两个元素是否同属于一个集合（至少一个）。所属集合可以用二进制表示法。

三 样例分析

3 // 表示3个集合

3 1 2 3 // 第1个集合包含3个元素 1 2 3

3 1 2 5 // 第2个集合包含3个元素 1 2 5

1 10    // 第3个集合包含1个元素 10

4 // 表示查询数

1 3 // 表示查询 1 和 3 是否同属于一个集合 s[1]&s[3]=0110&0010=0010,统计1的个数，即1和3同属于集合的个数，输出“YES”

1 5 // s[1]&s[5] = 0110 & 0100 = 0100,统计1的个数为1，输出“YES”

3 5 // s[3]&s[5] = 0010 & 0100 = 0000,统计1的个数为0，输出“NO”

1 10 // s[1]&s[10] = 0110 & 1000 = 0000,统计1的个数为0，输出“NO”

采用 BitSet 类解决

1 定义一个 BitSet 数组，对每个数都用二进制表示。

2 根据输入数据，将元素所属集合对应的位置为1。

3 根据查询输入的两个数 x,y,统计s[x]&s[y]运算后二机制数中1的个数，如果大于或等于1，则输出“YES”，否则输出 “NO” 。

四 实现

package bitdemo;

import java.util.BitSet;
import java.util.Scanner;

public class BitSetTest {
    public static void main(String[] args) {
        BitSet s[] = new BitSet[10010];
        for (int i = 0; i < s.length; i++) {
            s[i] = new BitSet();
        }
        // 表示集合数
        int n;
        // 表示待查询数
        int q;
        // 表示每个集合有几个元素
        int num;
        // 待比较的第1个数
        int x;
        // 待比较的第2个数
        int y;
        // 表示输入的数
        int item;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            num = scanner.nextInt();
            while (num-- > 0) {
                item = scanner.nextInt();
                // 设置该元素属于哪个集合
                s[item].set(i);
            }
        }
        q = scanner.nextInt();
        while (q-- > 0) {
            x = scanner.nextInt();
            y = scanner.nextInt();
            BitSet object = (BitSet) s[x].clone();
            object.and(s[y]);
            if (object.isEmpty()) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}

五 测试

绿色为输入，白色为输出。