【BFS】微博转发

【BFS】微博转发

题目

1562. 微博转发 - AcWing题库

---

微博被称为中文版的 Twitter。

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

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

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

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

补充

如果 $B$ 是 $A$ 的关注者， $C$ 是 $B$ 的关注者，那么 $A$ 的第一层关注者是 $B$ ，第二层关注者是 $C$ 。

输入格式

第一行包含两个整数， $N$ 表示用户数量， $L$ 表示需要考虑的关注者的层数。

假设，所有的用户的编号为 $1 \sim N$ 。

接下来 $N$ 行，每行包含一个用户的关注信息，格式如下：

M[i] user_list[i]

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

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

输出格式

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

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

数据范围

$1 \le N \le 1000$ ,
$1 \le L \le 6$ ,
$1 \le M[i] \le 100$ ,
$1 \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);
        }
    }
}