PAT 1076 Forwards on Weibo

这一题的意思是给出N个用户，每一个用户都有关注的人，当一个用户发布海报的时候，关注它的人（粉丝）可以转发，现在让我们统计，当一个用户发表海报的时候，有多少个用户转发它。题目上要求最多能有L层转发。
很明显要建图，因为题目上要求有L层，这很明显的会涉及bfs。
而建图的时候采用邻接表建图，把每一个用户当作一个顶点，它的粉丝相当于与它相连的顶点。
要找L层内有多少个用户能转发某一个用户的海报时，只需要bfs遍历L层
因此只需要建好图，然后用bfs进行遍历寻找即可。
完整代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
using namespace std;
int N; 
int L;
struct node
{int M;int user_list[105];
}people[1005];
vector<vector<int>>g(1005);
queue<int> q;
bool flag[1005];
int bfs(int x,int l)
{int cnt=0;flag[x]=1;for(int i=0;i<g[x].size();i++){if(flag[g[x][i]]==0){flag[g[x][i]]=1;q.push(g[x][i]);cnt++;}}l--;while(l){queue<int> temp;while(!q.empty()){int j=q.front();q.pop();for(int i=0;i<g[j].size();i++){if(flag[g[j][i]]==0){flag[g[j][i]]=1;temp.push(g[j][i]);cnt++;}}	}l--;q=temp;}return cnt;
}
int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(cin>>N>>L;for(int i=1;i<=N;i++){cin>>people[i].M;for(int j=0;j<people[i].M;j++){cin>>people[i].user_list[j];g[people[i].user_list[j]].push_back(i);}}int K;cin>>K;for(int i=0;i<K;i++){int temp;cin>>temp;memset(flag,0,sizeof(flag));int cnt=bfs(temp,L);cout<<cnt<<endl;	} return 0;} 

注意：
1.我在写这道题的时候，很长时间都没有弄清题意，原因是我以为
下面这句话的意思是，用户i有M[i]个粉丝,而实际上是用户i关注了M[i]个人
是因为英语的原因，没读懂题意
user[i] follows表示用户i跟随/关注别人

where M[i] (≤100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that followed by user[i].

因为这的原因，导致我一直都没有弄清楚题目给的例子。
2.测试用例中给出6这个用户，最后输出的结果是5，表示在L层内共有5个人会转发
我在模拟测试用例的时候刚开始得出的是6，原因是在bfs遍历的过程中可能会遍历到原点，不能访问原点。
因此，我们应该提前对所有的点进行一个标记是否访问过，访问过的不再重复访问。
总结：弄清题意后，只需要掌握基本的图的构建和bfs即可解决这一题。