《蓝桥杯每日一题》bfs·AcWing1562. 微博转发_bfs试炼之微博转发

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++;
    }
}

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