题目描述

C++代码

样例

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int M = 1010;
typedef long long ll;
int N, L, K;
int k[M];
int mm[M];
int user_list[M];
bool vis[M];
struct userID {
    vector<int> m;
    int len;
}user[M];
ll ans = 0;
void bfs(int id)
{
    queue<pair<int, int>> q;
    q.push({id,1});
    while (!q.empty())
    {
        auto top = q.front();
        q.pop();
        int frist = top.first;
        int second = top.second;
        for (int i = 0; i < user[frist].len; i++)
        {
            //不推荐这种写法，因为可能还要将最高层的用户编号入队列，但是已经判断过最高层的用户是否转发过了
//          if (vis[user[frist].m[i]] == false && second<=L)
//          {
//              ans += 1;
//              vis[user[frist].m[i]] = true;
//              q.push({ user[frist].m[i],second + 1 });
//              if (second < L)
//              {
//                  q.push({ user[frist].m[i],second + 1 });
//              }
//          }

            //推荐这种写法
            if (vis[user[frist].m[i]] == false)
            {
                ans += 1;
                vis[user[frist].m[i]] = true;
                if (second < L)
                {
                    q.push({ user[frist].m[i],second + 1 });
                }
            }
        }
    }
}
int main()
{
    cin >> N >> L;
    int n = N;
    int p = 1;
    while (n--)
    {
        cin >> mm[p];
        for (int i = 0; i < mm[p]; i++)
        {
            int x;
            cin >> x;
            user[x].m.push_back(p);
            user[x].len++;
        }
        ++p;
    }
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        cin >> k[i];
    }
    for (int i = 0; i < K; i++)
    {
        ans = 0;
        memset(vis, false, sizeof vis);
        vis[k[i]] = true;
        bfs(k[i]);
        cout << ans << endl;
    }
    return 0;
}