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 q=new LinkedList<>();q.offer(x);st[x]=true;int res=0;//枚举每一层层数for(int i=0;i0) {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++;}
}

感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下