公司品牌网站设计,网站用橙色,佛山做一个自己的网站,网站建设公司华网天下买2年送2年题意#xff1a;给出关注列表#xff0c;博主的粉丝会给博主点赞#xff0c;粉丝的粉丝也会给博主点赞#xff0c;一直递推到最多L层#xff0c;求#xff0c;最后会有多少人给博主点赞。
思路#xff1a;将关注的粉丝用链接表存储#xff0c;再对博主进行层序遍历给出关注列表博主的粉丝会给博主点赞粉丝的粉丝也会给博主点赞一直递推到最多L层求最后会有多少人给博主点赞。
思路将关注的粉丝用链接表存储再对博主进行层序遍历遍历L1层因为不能包含博主层并且将遍历过的人都标记防止重复计算同时算出所有遍历到的所有结点。结点数-1不包含博主即为答案。
刚开始写了个深度为L1的深度优先遍历结果不对因为深度遍历过的结点可能会与后面的兄弟结点重复造成提前标记故只能使用层序遍历
#includebits/stdc.h
using namespace std;vectorintson[1010];
bool vis[1010];
int bfs(int u,int k){memset(vis,0,sizeof vis);queueintq;q.push(u);k;int res0;while(q.size()k--){int lenq.size();while(len--){int fq.front();q.pop();if(vis[f])continue;//防止重复计算res;vis[f]1;for(auto x:son[f]){if(!vis[x]){q.push(x);}}}}return res;
}
int main(){int n,k;cinnk;for(int i1;in;i){int m;cinm;while(m--){int a;cina;son[a].push_back(i);}}int q;cinq;while(q--){int a;cina;coutbfs(a,k)-1endl;}
}
