微博被称为中文版的 Twitter。
微博上的用户既可能有很多关注者,也可能关注很多其他用户。
因此,形成了一种基于这些关注关系的社交网络。
当用户在微博上发布帖子时,他/她的所有关注者都可以查看并转发他/她的帖子,然后这些人的关注者可以对内容再次转发…
现在给定一个社交网络,假设只考虑 L 层关注者,请你计算某些用户的帖子的最大可能转发量。
补充
如果 B是 A的关注者,C 是 B 的关注者,那么A 的第一层关注者是 B,第二层关注者是 C。
输入格式
第一行包含两个整数,N 表示用户数量,L 表示需要考虑的关注者的层数。
假设,所有的用户的编号为 1∼N。
接下来 N 行,每行包含一个用户的关注信息,格式如下:
M[i] user_list[i]
M[i]
是第 ii 名用户关注的总人数,user_list[i]
是第 ii 名用户关注的 M[i]
个用户的编号列表。
最后一行首先包含一个整数 K,表示询问次数,然后包含 K 个用户编号,表示询问这些人的帖子的最大可能转发量。
输出格式
按顺序,每行输出一个被询问人的帖子最大可能转发量。
假设每名用户初次看到帖子时,都会转发帖子,只考虑 LL 层关注者。
数据范围
1≤N≤1000
1≤L≤6
1≤M[i]≤100
1≤K≤N
输入样例:
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
输出样例:
4
5
代码
思路
1.使用邻接表存储数据,将数据构造为有向图
2.使用bfs广搜,每个用户搜索L层,每次找到到一个新的用户,就把结果+1
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 1010,M = 100010; int h[N],e[M],ne[M],idx; bool st[N]; int n,L; void add(int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx++; } int bfs(int start) { queue<int> q; memset(st,0,sizeof st); q.push(start); st[start] = true; int res = 0; for(int i = 0;i < L;i++) { int sz = q.size(); while (sz--) { int t = q.front(); q.pop(); for(int j = h[t];j != -1;j = ne[j]) { int x = e[j]; if (!st[x]) { q.push(x); st[x] = true; res++; } } } } return res; } int main() { scanf("%d%d",&n,&L); memset(h,-1,sizeof h); for(int i = 1;i <= n;i++) { int cnt; scanf("%d",&cnt); while (cnt--) { int x; scanf("%d",&x); add(x,i); } } int m; scanf("%d\n",&m); while (m--) { int x; scanf("%d",&x); printf("%d\n",bfs(x)); } return 0; }
标签:int,用户,st,帖子,微博,关注,转发,1562,AcWing
From: https://www.cnblogs.com/polang19/p/17169737.html