个人练习-PAT甲级-1076 Forwards on Weibo

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736

开始用dijkstra，把follow距离当作1，结果超时了。。。那么就是图的BFS问题，最深层数为L。然而忘记BFS怎么写了。。自己写了一个，最后一个点一直超时，然后照着柳神的抄了一遍（BFS部分），提交发现还是最后一个点超时，于是把每个人的fans的存储从set改成了vector，然后就过了。。。

这篇就写全一点好了
读取输入，注意给的是每个人followings的列表，我们要转换为每个人的fans列表。

    for (int i = 1; i <= N; i++) {
    int M;scanf("%d", &M);for (int j = 0; j < M; j++) {
    int tmp;scanf("%d", &tmp);cf[tmp].push_back(i);}}

存储的类，包含id和层数lvl

class Node {
    
public:int id, lvl;Node() {
    }Node(int id, int lvl) {
    this->id = id;this->lvl = lvl;}
};

BFS部分
创建队列，把第一个Nodet压进队列，标记inq[t]=true，表示它已经进过队列了，然后在队列为空之前循环：

bool inq[1002] = {
     false };queue<Node> q;q.push(t);inq[t.id] = true;int cnt = 0;

将队列最前部的Nodetop取出，如果层数小于L就继续，否则就要停下来了。
对top的每一个fan，如果这个fan没有进过队列，就将它的id取出，并将lvl置为top的层数+1，组成新Node，放进队列，计数cnt++

    while (!q.empty()) {
    Node top = q.front();q.pop();int top_id = top.id;if (top.lvl < L){
    for (int i = 0; i < cf[top_id].size(); i++) {
    int next_id = cf[top_id][i];if (!inq[next_id]){
    Node nxt(next_id, top.lvl + 1);q.push(nxt);inq[nxt.id] = true;cnt++;}}}}

最后把cnt返回，BFS就结束了

输出，用一个初始都为-1的数组ret存BFS的结果。这样的话，如果每次query读入的是相同的节点，就不需要重新bfs一遍了。

    scanf("%d", &K);for (int i = 0; i < K; i++) {
    int s;scanf("%d", &s);if (ret[s] < 0){
    Node t(s, 0);int tmp_ret = bfs(t);ret[s] = tmp_ret;}printf("%d\n", ret[s]);}

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;int N, L, K;
vector<vector<int>> cf;class Node {
    
public:int id, lvl;Node() {
    }Node(int id, int lvl) {
    this->id = id;this->lvl = lvl;}
};int bfs(Node t) {
    bool inq[1002] = {
     false };queue<Node> q;q.push(t);inq[t.id] = true;int cnt = 0;while (!q.empty()) {
    Node top = q.front();q.pop();int top_id = top.id;if (top.lvl < L){
    for (int i = 0; i < cf[top_id].size(); i++) {
    int next_id = cf[top_id][i];if (!inq[next_id]){
    Node nxt(next_id, top.lvl + 1);q.push(nxt);inq[nxt.id] = true;cnt++;}}}}return cnt;
}int main() {
    scanf("%d %d", &N, &L);cf.resize(N + 1);vector<int> ret(N+1, -1);for (int i = 1; i <= N; i++) {
    int M;scanf("%d", &M);for (int j = 0; j < M; j++) {
    int tmp;scanf("%d", &tmp);cf[tmp].push_back(i);}}scanf("%d", &K);for (int i = 0; i < K; i++) {
    int s;scanf("%d", &s);if (ret[s] < 0){
    Node t(s, 0);int tmp_ret = bfs(t);ret[s] = tmp_ret;}printf("%d\n", ret[s]);}return 0;
}