L2-049 鱼与熊掌 #反向建图

2025/4/7 21:47:17 来源：https://blog.csdn.net/mzh1213/article/details/147021177 浏览: 次关键词：L2-049 鱼与熊掌 #反向建图

文章目录

题目解读
思路
AC CODE
参考
注意

题目解读

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

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

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

思路

反向建图,建立人指向物品的图
这样对于指定的物品,我们只需要遍历该物品被谁拥有
暴力可解

AC CODE

#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;vector<int> g[N];
map<int,bool> mp;
int cnt;int main(){int n,m;cin >> n >> m;for(int i=1; i<=n; i++){int k;cin >> k;for(int j=0; j<k; j++){int x;cin >> x;//建立人指向物品的图//即该物品被哪些人拥有g[x].push_back(i); }}int q;cin >> q;for(int i=0; i<q; i++){cnt=0;int a,b;cin >> a >> b;//遍历物品a和物品bfor(int i=0; i<g[a].size(); i++){mp[g[a][i]]=1;} for(int i=0; i<g[b].size(); i++){if(mp[g[b][i]] == 1)cnt++;}cout << cnt;if(i!=q-1)cout << endl;} return 0;
}