1076 Forwards on Weibo （链接表层序遍历）

本文主要是介绍1076 Forwards on Weibo （链接表层序遍历），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 题意：给出关注列表，博主的粉丝会给博主点赞，粉丝的粉丝也会给博主点赞，一直递推到最多L层，求，最后会有多少人给博主点赞。

思路：将关注的粉丝用链接表存储，再对博主进行层序遍历，遍历L+1层（因为不能包含博主层），并且将遍历过的人都标记防止重复计算，同时算出所有遍历到的所有结点。结点数-1（不包含博主）即为答案。

（刚开始写了个深度为L+1的深度优先遍历，结果不对，因为深度遍历过的结点可能会与后面的兄弟结点重复，造成提前标记，故只能使用层序遍历）

#include<bits/stdc++.h>
using namespace std;vector<int>son[1010];
bool vis[1010];
int bfs(int u,int k){memset(vis,0,sizeof vis);queue<int>q;q.push(u);k++;int res=0;while(q.size()&&k--){int len=q.size();while(len--){int f=q.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;cin>>n>>k;for(int i=1;i<=n;i++){int m;cin>>m;while(m--){int a;cin>>a;son[a].push_back(i);}}int q;cin>>q;while(q--){int a;cin>>a;cout<<bfs(a,k)-1<<endl;}
}

这篇关于1076 Forwards on Weibo （链接表层序遍历）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---