共计 1718 个字符，预计需要花费 5 分钟才能阅读完成。
题目粗心：
在微博中，每个用户都可能被若干其余用户关注。而当该用户公布一条音讯时，关注他的人就能够看到这条信息并且抉择是否转发它，且转发的音讯也能够被关注他的人再次转发, 然而同一用户最多转发该信息一次 (信息的最后发布者不能转发该音讯), 当初给出 N 个用户的关注状况以及一个转发层数下限 L，并给出最后公布音讯的用户编号，求在转发层数下限内音讯最多会被多少用户转发
算法思路：
首先得了解题意
assuming that only L levels of indirect followers are counted.
这里的 $indirect$ $followers$ 指的是除了发布者以外的关注他的人, 而不是在所有关注者中除了第一个关注者之外的人
calculate the maximum potential amount of forwards for any specific user
这句话指的是计算 L 层内的所有不同的人有多少个,$potential$ $ amount$ 就是可能转发的意思，其实就是以发布者为核心的 L 层内的总人数, 对于人 A 有关注 A 的人 B 存在, 那么 A 公布的微博 B 是能够看的到的, 那么就存在一条微博传递门路 $A->B$, 对于输出中 $user[i]$ 和 $userlist[i]$ 实际上是 $user[i]$ 关注了 $userlist[i]$, 所以有一条 $userlist[i]->user[i]$ 的微博传递门路。
在了解题意后很分明的晓得咱们要求的是在发布者为核心流传 L 层内的所有人数, 很天然就联想到广度优先遍历的办法求解此题。为了不便的记录每一个节点的层数从而统计 L 层内的人数，咱们建设构造体 Node 将人员的编号和层数进行绑定，而后在广度优先遍历的时候，每次出队的时候，只有出队节点的层数大于 L，间接退出循环，否则就统计除了自己的转发人数。
留神点：
- 1、应用 DFS 最初一个测试点会超时。
- 2、每一个人只能转发一次，须要去重，能够应用 $unordered$_$set$ 解决，这里应用了入队标记数组。
- 3、每次查问须要初始化 $visited$
- 4、存储数组大小得开到 1001 以上否则最初一组测试点呈现运行时谬误。
提交后果：
AC 代码：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct Node{
int index;
int level;
};
int N,L;// 总人数，层数
vector<int> G[1001];// 设置为 1000 会导致测试点 4 运行时谬误
bool visited[1001];// 入队标记数组
void BFS(int start){
queue<Node> q;
q.push(Node{start,0});
int count = 0;// 统计 L 层内的人数
visited[start] = true;
while(!q.empty()){Node top = q.front();
q.pop();
if(top.level>L){break;} else {
// 不统计本人
if(top.index!=start) ++count;
for(int i=0;i<G[top.index].size();++i){int next = G[top.index][i];
if(!visited[next]){visited[next] = true;
q.push(Node{next,top.level+1});
}
}
}
}
printf("%d\n",count);
}
int main()
{scanf("%d %d",&N,&L);
int num,followed;
for (int i = 1; i <= N; ++i) {scanf("%d",&num);
for (int j = 0; j < num; ++j) {scanf("%d",&followed);
G[followed].push_back(i);
}
}
int K,user;
scanf("%d",&K);
// K 个查问
for(int i=0;i<K;++i){scanf("%d",&user);
memset(visited,0, sizeof(visited));
BFS(user);
}
return 0;
}
