1076. Forwards on Weibo.md

pat甲级1076. Forwards on Weibo

题意概述

给出每个用户关注的人，问如果给定的人发了一条微博，在所给的最大转发层数下，最多有多少个人会转发。注意给出的是每个用户关注的人，而不是关注该用户的人。

输入输出格式

输入第一行包含2个正整数：N、L，分别表示用户数、被计数的间接关注者的级别数。所有用户从1到N编号。接下来N行，每行的格式为M[i] user_list[i]，其中M[i]是用户i关注的总人数； user_list[i]是用户i关注的人的编号。保证没有人关注自己。所有数字都用空格分隔。最后一行先给出一个正整数K，后跟K个用户ID进行查询。

对于每个查询，假设每个查看初始帖子的用户都将转发一次，并且只计算L级间接关注者，在一行中打印出该用户可以触发的最大潜在转发量。

算法设计

从查询ID发起广度优先遍历，统计L层以内间接关注者的总数即可。

注意点

不能使用深度优先遍历，这是因为图中可能有多条路径可以到达某个用户，用深度优先遍历的话，该用户可能会处于多个层级，我们只需考虑最小的层级。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 1005;
vector<bool> inQueue(MAX);
vector<vector<gg>> graph(MAX);
gg ni, li, mi, ai;
gg bfs(gg v) {
    fill(inQueue.begin(), inQueue.end(), false);
    queue<gg> q;
    q.push(v);
    inQueue[v] = true;
    gg ans = 0;
    for (gg level = 0; not q.empty() and level < li; ++level) {
        gg s = q.size();
        for (gg t = 0; t < s; ++t) {
            v = q.front();
            q.pop();
            for (gg i : graph[v]) {
                if (not inQueue[i]) {
                    q.push(i);
                    ++ans;
                    inQueue[i] = true;
                }
            }
        }
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni >> li;
    for (gg i = 1; i <= ni; ++i) {
        cin >> mi;
        while (mi--) {
            cin >> ai;
            graph[ai].push_back(i);
        }
    }
    cin >> mi;
    while (mi--) {
        cin >> ai;
        cout << bfs(ai) << "\n";
    }
    return 0;
}