PAT 1076. 微博转发
原题链接
中等
作者:
YAX_AC
,
2024-11-18 15:17:33
,
所有人可见
,
阅读 2
//you are supposed to calculate the maximum potential amount of forwards for any specific user,
//assuming that only L levels of indirect followers are counted.
//现在给定一个社交网络,假设只考虑L层关注者,请你计算某些用户的帖子的最大可能转发量
//the number of levels of indirect followers that are counted
//计算的间接追随者级别数 are counted被计算
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1010, M = 1e5 + 10;
int n,L;
int h[N], ne[M], e[M], idx;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs(int start)
{
queue<int>q;
memset(st,0,sizeof st);
q.push(start);
st[start] = true;
int res = 0;
for(int i = 0; i<L; i++)//一次会刚好往队列里加一层的所有点 所以做L次
{
int sz = q.size();//当前队列刚好储存了该层的全部节点 所以算把q.size次就能刚好把这一层算完
while(sz--)
{
int t = q.front();
q.pop();
for(int j = h[t]; j != -1; j = ne[j])//遍历该点的全部下一层子节点加进队列 这样做完sz次之后就刚好把下一层的全部节点加进队列
{
int x = e[j];
if(!st[x])
{
q.push(x);
st[x] = true;
res++;
}
}
}
}
return res;
}
int main()
{
cin>>n>>L;
memset(h,-1,sizeof h);
//M[i] user_list[i]
//M[i] 是第 i 名用户关注的总人数,user_list[i] 是第 i 名用户关注的 M[i] 个用户的编号列表。
for(int i = 1; i<=n; i++)
{
int cnt;
cin>>cnt;
while(cnt--)
{
int x;
cin>>x;
add(x, i);//因为点x被第i点所关注所以会被转发到i点 因此从点x连接到点i
}
}
int k;
cin>>k;
for(int i = 0; i<k; i++)
{
int x;
cin>>x;
cout<<bfs(x)<<endl;
}
return 0;
}