摘要
Title: 1562. 微博转发
Tag: BFS
Memory Limit: 64 MB
Time Limit: 1000 ms

1562. 微博转发

题意

微博被称为中文版的 Twitter。
微博上的用户既可能有很多关注者，也可能关注很多其他用户。
因此，形成了一种基于这些关注关系的社交网络。
当用户在微博上发布帖子时，他/她的所有关注者都可以查看并转发他/她的帖子，然后这些人的关注者可以对内容再次转发…
现在给定一个社交网络，假设只考虑 L层关注者，请你计算某些用户的帖子的最大可能转发量。
思路

正常图的遍历即可

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

vector<int> g[N];
int st[N];

signed main()
{
    IOS;
    int n, l;
    cin >> n >> l;
    for (int i = 1; i <= n; ++i)
    {
        int m;
        cin >> m;
        while (m--)
        {
            int x;
            cin >> x;
            g[x].push_back(i);
        }
    }

    auto bfs = [&](int x) {
        queue<PII> q;
        q.push({x, 1});
        memset(st, 0, sizeof st);
        st[x] = 1;
        int ans = 0;
        while (SZ(q))
        {
            auto [u, cnt] = q.front();
            q.pop();
            if (cnt > l)
                return ans;
            for (auto v : g[u])
            {
                if (!st[v])
                {
                    ans++;
                    st[v] = 1;
                    q.push({v, cnt + 1});
                }
            }
        }
        return ans;
    };

    int k;
    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        int x;
        cin >> x;
        cout << bfs(x) << '\n';
    }
    return 0;
}

1562. 微博转发

题意

思路

代码