题目描述

《孟子 · 告子上》有名言：“鱼，我所欲也，熊掌，亦我所欲也；二者不可得兼，舍鱼而取熊掌者也。”但这世界上还是有一些人可以做到鱼与熊掌兼得的。
给定 n 个人对 m 种物品的拥有关系。对其中任意一对物品种类（例如“鱼与熊掌”），请你统计有多少人能够兼得？

输入格式

输入首先在第一行给出 2 个正整数，分别是： n (\le 10 ^ 3) 为总人数（所有人从 1 到 n 编号）、 m (2\le m \le 10 ^ 9) 为物品种类的总数（所有物品种类从 1 到 m 编号）。
随后 n 行，第 i 行 (1\le i \le n) 给出编号为 i 的人所拥有的物品种类清单，格式为：

K M[1] M[2] ... M[K]

其中 K (\le 10 ^ 3) 是该人拥有的物品种类数量，后面的 M[*] 是物品种类的编号。题目保证每个人的物品种类清单中都没有重复给出的种类。
最后是查询信息：首先在一行中给出查询总量 Q (\le 10 ^ 3) ，随后 Q 行，每行给出一对物品种类编号，其间以空格分隔。题目保证物品种类编号都是合法存在的。

输出格式

对每一次查询，在一行中输出两种物品兼得的人数。

输入样例

4 8
3 4 1 8
4 7 1 8 4
5 6 5 1 2 3
4 3 2 4 8
3
2 3
7 6
8 4

输出样例

2
0
3

题意

给出 n 个序列，查询 Q 次，问有多少个序列同时含有询问的两个不同数字。

思路

将每个序列的内容存进 unordered_set，每次询问的时候遍历所有序列，用 find 函数查找是否同时包含即可。

时间复杂度 O(nQ) 。

代码

void solve(){
    int n,m;
    cin >> n >> m;
    vector<unordered_set<int>> a (n);
    for(int i = 0;i < n;i++){
        int k;
        cin >> k;
        for(int j = 0;j < k;j++){
            int x;
            cin >> x;
            a[i].insert(x);
        }
    }
    int q;
    cin >> q;
    while(q--){
        int u,v;
        cin >> u >> v;
        int ans = 0;
        for(int i = 0;i < n;i++){
            if(a[i].find(u) != a[i].end() && a[i].find(v) != a[i].end()){
                ans++;
            }
        }
        cout << ans << "\n";
    }
}