今日的知识点为 \(BFS\) (广度优先搜素)。
\(BFS\)
简要介绍下 \(BFS\) 算法。首先，\(BFS\) 算法适用于边权为 \(1\) 的图论问题。\(BFS\) 算法的解题思路也比较固定。确定初始状态，然后对初始状态拓展。大致的解题模板如下
初始化 queue
while queue 不空
{
t 为队头
for (拓展队头)
{
if (!st) 加至队尾
}
}
那么由上可见 \(BFS\) 算法离不开队列(\(queue\))以及判重数组(\(st\))。大多数情况下，在入队时，需要进行判重，确保每个点只遍历一次。
AcWing1562.微博转发
题目描述
微博被称为中文版的 \(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
解题思路
我们如何使用 \(BFS\) 算法解这道题。首先，这道题是给定我们层数限制，尽可能多的拓展，和 \(BFS\) 算法的思想很契合。那么我们就可以先采用邻接表来存储所有的信息，被关注着者为表头，关注者为节点。在最初的提交时，笔者忽视了层数限制这一条件，这里笔者使用的是记录每个用户的层数，关注者层数=被关注者层数+1。当我们要拓展的关注者其所在的层数到达限制时，我们就不再进行拓展了，就可以 break。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 100010;
typedef pair<int, int> PII;
int n, L, K;
int h[N], e[M], ne[M], idx;
bool st[N];
PII q[N]; // first为点，second为层
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
int bfs(int u)
{
int hh = 0, tt = -1;
q[++ tt] = {u, 0};
st[u] = true;
while (hh <= tt)
{
auto t = q[hh ++];
if (t.second == L) break;
for (int i = h[t.first]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
q[++ tt] = {j, t.second + 1};
st[j] = true;
}
}
}
return tt;
}
int main()
{
scanf("%d%d", &n, &L);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++)
{
int m;
scanf("%d", &m);
while (m --)
{
int j;
scanf("%d", &j);
add(j, i); // i关注j
// cout << j << ' ' << i << ' ';
}
}
scanf("%d", &K);
while (K --)
{
memset(st, 0, sizeof st);
int u;
scanf("%d", &u);
printf("%d\n", bfs(u));
}
return 0;
}