侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 667 篇文章
  • 累计创建 127 个标签
  • 累计收到 15 条评论

目 录CONTENT

文章目录

【BFS】微博转发

GabrielxD
2023-02-28 / 0 评论 / 0 点赞 / 71 阅读 / 855 字
温馨提示:
本文最后更新于 2023-02-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

【BFS】微博转发

题目

1562. 微博转发 - AcWing题库


微博被称为中文版的 Twitter。

微博上的用户既可能有很多关注者,也可能关注很多其他用户。

因此,形成了一种基于这些关注关系的社交网络。

当用户在微博上发布帖子时,他/她的所有关注者都可以查看并转发他/她的帖子,然后这些人的关注者可以对内容再次转发…

现在给定一个社交网络,假设只考虑 LL 层关注者,请你计算某些用户的帖子的最大可能转发量。

补充

如果 BBAA 的关注者, CCBB 的关注者,那么 AA 的第一层关注者是 BB ,第二层关注者是 CC

输入格式

第一行包含两个整数, NN 表示用户数量, LL 表示需要考虑的关注者的层数。

假设,所有的用户的编号为 1N1 \sim N

接下来 NN 行,每行包含一个用户的关注信息,格式如下:

M[i] user_list[i]

M[i] 是第 ii 名用户关注的总人数,user_list[i] 是第 ii 名用户关注的 M[i] 个用户的编号列表。

最后一行首先包含一个整数 KK ,表示询问次数,然后包含 KK 个用户编号,表示询问这些人的帖子的最大可能转发量。

输出格式

按顺序,每行输出一个被询问人的帖子最大可能转发量。

假设每名用户初次看到帖子时,都会转发帖子,只考虑 LL 层关注者。

数据范围

1N10001 \le N \le 1000 ,
1L61 \le L \le 6 ,
1M[i]1001 \le M[i] \le 100 ,
1KN1 \le K \le 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

解题

方法一:BFS

思路

BFS简单题,套模板就能做,这里提一下需要注意的地方:

  • user_list 是关注列表,不是粉丝列表,要维护的是粉丝列表。
  • 求的是最大可能转发量,所以用户自己第一次发的不算数。
  • 每算完一个用户的帖子最大可能转发量之后要清空队列与 vis 数组,否则会影响到下一次的结果。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int l = (int) in.nval;
        List<Integer>[] follows = new ArrayList[n + 1];
        for (int i = 1; i <= n; ++i) follows[i] = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            int m = (int) in.nval;
            while (m-- > 0) {
                in.nextToken();
                int sub = (int) in.nval;
                follows[sub].add(i);
            }
        }
        in.nextToken();
        int k = (int) in.nval;
        boolean[] vis = new boolean[n + 1];
        Queue<Integer> que = new LinkedList<>();
        while (k-- > 0) {
            que.clear();
            Arrays.fill(vis, false);
            in.nextToken();
            int x = (int) in.nval;
            int cnt = 0;
            que.offer(x);
            vis[x] = true;
            for (int i = 0; i < l; ++i) {
                int sz = que.size();
                while (sz-- > 0) {
                    int curr = que.poll();
                    for (int follow : follows[curr]) {
                        if (!vis[follow]) {
                            que.offer(follow);
                            vis[follow] = true;
                            ++cnt;
                        }
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}
0

评论区