题目大意：给出每个用户id关注的人，和转发最多的层数L，求一个id发了条微博最多会有多少个人转发，
每个人只考虑转发一次。
用BFS，同时每个节点要记录下所在的层数，由于只能转发一次，所以每个节点要用vis判断之前是否入过队列，不能重复入队。
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> #include <queue> using namespace std; const int maxn=1005; int vis[maxn]; int head[maxn]; int tot; int ans=0; struct Edge{ int to; int next; }edge[maxn*100]; void init(){ tot=0; memset(head,-1,sizeof(head)); } void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } struct Node{ int u; int layer; }; void BFS(int u,int L){ queue<Node> q; Node s,tmp; s.u=u; s.layer=0; q.push(s); while(!q.empty()){ tmp=q.front(); q.pop(); if(tmp.layer>L) break; if(tmp.layer!=0) ans++; for(int k=head[tmp.u];k!=-1;k=edge[k].next){ int v=edge[k].to; if(!vis[v]){ s.u=v; s.layer=tmp.layer+1; vis[v]=1; //要注意这里就要标记vis=1，而不是从队列里取出来时标记，会超时。 q.push(s); } } } } int main() { int n,l,m,k,v; init(); scanf("%d %d",&n,&l); for(int i=1;i<=n;i++){ scanf("%d",&m); for(int j=0;j<m;j++){ //注意题目，是i关注了m个人，也就是这m个人发布的消息能被i看到，建立v->i的边 scanf("%d",&v); add(v,i); } } int id; scanf("%d",&k); for(int i=0;i<k;i++){ scanf("%d",&id); memset(vis,0,sizeof(vis)); vis[id]=1; ans=0; //dfs(id,0,l+1,id); BFS(id,l); printf("%d ",ans); } return 0; }