一、题目
1、原题链接
1562. 微博转发
2、题目描述
微博被称为中文版的 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
1
2
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）可以将本题关系存储在图中，将每个人和他的粉丝之间连一条有向边，由被关注者指向粉丝。
（2）该问题就变成了从每个人开始，经过的边数不超过l可以到达的点数，即为答案。
（3）可以利用宽搜来实现，从询问的人开始搜索l层，统计可以到达的点数即为答案。
2、时间复杂度
时间复杂度为O(k(n+m))（k为询问数，n为点数，m为边数，宽搜时间复杂度为O(n+m)）
3、代码详解
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=1010,M=100010; //N代表点数，M代表边数
int n,l,k;
int h[N],e[M],ne[M],idx; //h[]存储每个点的第一条边的编号，e[]存储每条边终点的值，ne[]存储每条边同起点的下一条边的编号，idx为边的编号
bool st[N]; //st[]存储每个点是否已经遍历过
//添加一条边a->b
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int bfs(int id){
int ans=0;
queue<int> q;
memset(st,0,sizeof st);
q.push(id);
st[id]=true;
//循环l层，统计ans
for(int i=0;i<l;i++){
int cnt=q.size(); //记录该层的点数
while(cnt--){ //依次遍历该层的每个点，将每个点可以到达且没有遍历过的点加入队列
int t=q.front();
q.pop();
//遍历每个点可以到达的点
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
st[j]=true;
q.push(j);
ans++;
}
}
}
}
return ans;
}
int main(){
cin>>n>>l;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int num,id;
cin>>num;
for(int j=0;j<num;j++){
cin>>id;
add(id,i); //添加一条边，由被关注者指向粉丝
}
}
cin>>k;
while(k--){
int m;
cin>>m;
cout<<bfs(m)<<endl;
}
return 0;
}
三、知识风暴
宽搜BFS
尽可能向横向搜索，具有“最短性”（边权都为1时可以用BFS求最短路）。
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45035 人正在系统学习中
