题目地址:https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736
题目解释:
在微博中,每个用户都可能被若干个其他用户关注。而当该用户发布一条消息时,他的关注者就可以看到这条消息并选择是否转发(forward)它,其转发的信息也可以被转发者的关注者再次转发,但同一用户最多只转发该消息一次(信息的最初发布者不会转发该信息)。现在给出N个用户的关注情况(即他们各自关注了哪些用户)以及一个转发层数上限L,并给出最初发布消息的用户编号,求在转发层数上限内消息最多被多少用户转发?
解题思路:
1.对于第i个用户user[i],每一行给出的是他的关注者,所以信息可以从他的关注者们转发到user[i]。所以对于有向图来说,应该是从关注者->user[i]。
2.有向图的BFS遍历,在遍历的过程中计算器numforward累加,注意控制条件层数L的限制。
注意如何建立邻接表!
ac代码:
注意:头文件要写规范<cstring>(C++)或者<string.h>(C),不能写成<string>否则即使本地编译器不报错,pat上也会报编译错误
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#define maxn 1010
#define INF 10000000000
using namespace std;
struct node{
int id;//编号
int layer;//层数
};
vector<node> adj[maxn];//邻接表
bool inq[maxn]={false};//是否在队列中
int bfs(int s,int L)
{
int numforward=0;
node start;
queue<node> q;
start.id=s;
start.layer=0;
q.push(start);
inq[start.id]=true;
while(!q.empty())
{
node topNode=q.front();
q.pop();
int u=topNode.id;
for(int i=0;i<adj[u].size();i++)
{
node next=adj[u][i];
next.layer=topNode.layer+1;
if(inq[next.id]==false && next.layer<=L)
{
q.push(next);
inq[next.id]=true;
numforward++;
}
}
}
return numforward;
}
int main()
{
int N,L,numquery,numfollow,idfollow,s;
node user;
cin>>N>>L;
for(int i=1;i<=N;i++)
{
user.id=i;
cin>>numfollow;
for(int j=0;j<numfollow;j++)
{
cin>>idfollow;
adj[idfollow].push_back(user);
}
}
cin>>numquery;
for(int i=0;i<numquery;i++)
{
memset(inq,false,sizeof(inq));//每次dfs之前都要初始化
cin>>s;
printf("%d\n",bfs(s,L));
}
return 0;
}