《蓝桥杯每日一题》bfs·AcWing1562. 微博转发
1.题目描述
微博被称为中文版的 Twitter。
微博上的用户既可能有很多关注者，也可能关注很多其他用户。
因此，形成了一种基于这些关注关系的社交网络。
当用户在微博上发布帖子时，他/她的所有关注者都可以查看并转发他/她的帖子，然后这些人的关注者可以对内容再次转发…
现在给定一个社交网络，假设只考虑 L 层关注者，请你计算某些用户的帖子的最大可能转发量。
补充
如果 B 是 A 的关注者，C 是 B 的关注者，那么 A 的第一层关注者是 B，第二层关注者是 C。
输入格式
第一行包含两个整数，N 表示用户数量，L 表示需要考虑的关注者的层数。
假设，所有的用户的编号为1~N。
接下来 N行，每行包含一个用户的关注信息，格式如下：
M[i] user_list[i]
M[i] 是第 i 名用户关注的总人数，user_list[i] 是第 i 名用户关注的 M[i] 个用户的编号列表。
最后一行首先包含一个整数 K，表示询问次数，然后包含 K 个用户编号，表示询问这些人的帖子的最大可能转发量。
输出格式
按顺序，每行输出一个被询问人的帖子最大可能转发量。
假设每名用户初次看到帖子时，都会转发帖子，只考虑 L 层关注者。
数据范围
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
2.题目思路
1号用户关注了2号，就连一条2到1得边，表示2发的微博会被1转发
当询问2号用户微博的转发量时，使用bfs从2号开始一层一层遍历可到达的点，遍历过程中记录层数，
注意层数不能超过题目要求的L
3.Ac代码
import java.util.*;
public class Main {
static int N=100010;
static int h[]=new int[N],e[]=new int[N],ne[]=new int[N];
static boolean st[] = new boolean[N];
static int n,l,idx;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt(); l=sc.nextInt();
Arrays.fill(h,-1);
//将每个人的关注者连向自己
for(int i=1;i<=n;i++){
int n1=sc.nextInt();
while (n1-->0){
int x=sc.nextInt();
//建邻接表
add(x,i);
}
}
int k=sc.nextInt();
while (k-->0){
int t=sc.nextInt();
System.out.println(bfs(t));
}
}
private static Integer bfs(int x){
Arrays.fill(st,false);
Queue<Integer> q=new LinkedList<>();
q.offer(x);
st[x]=true;
int res=0;
//枚举每一层层数
for(int i=0;i<l;i++){
int size=q.size();
/* 枚举每一层的每一个点 判断该点的子节点是否被枚举过
如果没有则把该子节点加入队列中 当枚举到这一层的最后一个点时
该层的点已被全部删除 此时队列里只有下一层的点了 while循环结束 继续for循环枚举下一层*/
while (size-->0) {
int t = q.poll();
for(int j=h[t];j!=-1;j=ne[j]){
int tt=e[j];
if(st[tt]==false){
q.offer(tt);
st[tt]=true;
res++;
}
}
}
}
return res;
}
private static void add(int a, int b) {
e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}
}感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
腾讯云开发者
