1076. Forwards on Weibo (30)（图论，

PAT-A1076，题目地址：https://www.patest.cn/contests/pat-a-practise/1076
这道题目就是一道宽搜的题目，新颖的考点在于限制了统计的level，等于在宽搜过程中，搜索的深度不是无限的，这一点可以通过连个queue来实现，每层分别交替出现在不同的队列，方便统计已经搜索的深度。
注意：

1. 发微博的本人不算转发者
2. 同一条微博不能被一个人多次转发（即图中有可能有环）
3. 题目给的信息是每个人follow了哪些人，我们要反向利用这个信息，找出每个人的followers，图的边由被follow的人指向自己的follower

代码如下：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Person{
    int id;
    bool forward; //记录这个用户是否已经转发过这条微博
    vector<int> followers; //每个人有哪些follower
    Person(): id(0), forward(false){}
};

void reset(Person* p, int n, queue<int>* q){ //在每次不同的查询之间重置一些信息
    for(int i = 1; i <= n; i++){
        p[i].forward = false;
    }
    for(int i = 0; i < 2; i++){
        while(!q[i].empty())
            q[i].pop();
    }
}

int main(){
    int n, l, k;
    cin >> n >> l;
    Person* persons = new Person[n+1];
    for(int i = 1; i <= n; i++){
        int count, tmp;
        cin >> count;
        for(int j = 0; j < count; j++){
            cin >> tmp;
            persons[tmp].followers.push_back(i); //注意此处记录的方式
        }
    }
    cin >> k;
    queue<int> q[2];
    while(k--){
        int count = 0, which = 0, level = 0;
        int check;
        cin >> check;
        reset(persons, n, q);
        q[0].push(check); //check是要查询的用户
        while(!q[0].empty() || !q[1].empty()){
            while(!q[which].empty()){ //队列为空说明已经搜索完一层了
                int now = q[which].front();
                q[which].pop();
                if(persons[now].forward == false){ //如果now用户没有转发过这条微博，则进行转发，并自己的followers放入队列
                    persons[now].forward = true;
                    count++;
                    int length = persons[now].followers.size();
                    for(int i = 0; i < length; i++){
                        q[1-which].push(persons[now].followers[i]); //注意入队是把自己的follower放进另外一个队列，否则无法区别他们在第几层
                    }
                }
            }
            which = 1 - which; //开始搜索下一层
            level++; //level-1 代表目前已经搜索过level-1层
            if(level > l) //level - 1 = l,则代表已经搜索过l层了，退出本次查询
                break;
        }
        cout << count - 1 << endl; //count实际上也把发表微博的本人记录了下来，因此-1才是转发数
    }
    return 0;

}