题目描述
题目要的是转发的人,转发的是粉丝,所以开始存每个人的粉丝,然后其实只要找到L-1的人的粉丝就可以了
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MX = 1005;
vector<int> v[MX];
int N,L;
queue<pair<int,int>> q;
int vis[MX];
int bfs(int x)
{
int res = 0;
q.push({x , 0});
vis[x] = 1;
while(!q.empty())
{
auto t = q.front();
q.pop();
for(auto it : v[t.first])
{
if(!vis[it])
{
res++;
if(t.second < L - 1) q.push({it , t.second + 1});
vis[it] = 1;
}
}
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> L;
for(int i = 1 ; i <= N ; i++)
{
int x;
cin >> x;
for(int j = 1 ; j <= x ; j++)
{
int y;
cin >> y;
v[y].push_back(i);
}
}
int k;
cin >> k;
while(k--)
{
int x,ans = 0;
cin >> x;
memset(vis , 0 , sizeof(vis));
ans = bfs(x);
cout << ans << endl;
}
return 0;
}