https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736
这一道题是典型的BFS题目 注意从第二行开始输入的是 用户i的关注的人数 以及关注的用户的编号 而这道题统计的是某一个用户发一个帖子，在他的粉丝都会转发且只转发一次的条件下，转发层数不超过L的转发总数。 所以建图的时候,j建立的有向边方向应该是用户i到粉丝的有向边。 如样例，第二行，需要在2号，3号，4号的子节点中加入1号。 建好图后，因为每个用户只能转发一次，用BFS遍历每个结点只能访问一次。 访问时当下一个结点的层级数不超过L且未被访问过则加入队列中。
具体代码如下
#include<bits/stdc++.h> using namespace std; struct node{ int n;//编号 int layer;//层级 node(int _n,int _l):n(_n),layer(_l){ }; }; const int maxn=1010; vector<node> nodes[maxn]; bool vis[maxn]; //是否加入队列中 int N,L;// N个user 最多L层间接转发 int bfs(int st){ int numforward=0; queue<node> q; q.push(node(st,0)); vis[st]=1; while(!q.empty()){ node p=q.front(); q.pop(); for(int i=0;i<nodes[p.n].size();i++){ node next=nodes[p.n][i]; next.layer=p.layer+1; if(!vis[next.n]&&next.layer<=L){ q.push(next); vis[next.n]=1; numforward++; } } } return numforward; } int main(){ freopen("test.txt","r",stdin); cin>>N>>L; node user(0,0); int followid,follownum;//关注人数 for(int i=1;i<=N;i++){ cin>>follownum; user.n=i; for(int j=0;j<follownum;j++){ cin>>followid; nodes[followid].push_back(user); } } int querynum,qid; cin>>querynum; for(int i=0;i<querynum;i++){ memset(vis,false,sizeof(vis)); cin>>qid; cout<<bfs(qid)<<endl; } }