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 33 2 3 402 5 62 3 12 3 41 41 52 2 6
输出样例：
45
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++; } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
