题目链接：点击打开链接
题目大意：给出每个用户关注的人的 id 和转发最多的层数，求一个 id 发了条微博最多会有多少个人转发？
解题思路：带层数的广度优先，因为一个用户只能转发一次，所以用 vis 判断当前结点是否入队过了，如果入队过了就不能重复入队（重复转发消息），控制不超过 L 层。
AC 代码
1.#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1010; struct node { int id,lvl; node(){} node(int id,int lvl):id(id),lvl(lvl){} }; int n,l; vector<int> v[maxn]; int bfs(int id) { int cnt=0, vis[maxn]={0}; vis[id]=1; queue<node> q; q.push(node(id,0)); node nd; while(!q.empty()) { nd=q.front(); q.pop(); int tid=nd.id, lvl=nd.lvl; for(int i=0;i<v[tid].size();i++) { int newid=v[tid][i]; if(!vis[newid] && lvl<l) { q.push(node(newid,lvl+1)); vis[newid]=1; cnt++; } } } return cnt; } int main() { int m,tid; scanf("%d%d",&n,&l); for(int i=1;i<=n;i++) { scanf("%d",&m); while(m--) { scanf("%d",&tid); v[tid].push_back(i); } } scanf("%d",&m); while(m--) { scanf("%d",&tid); printf("%d\n",bfs(tid)); } return 0; }
