1076 Forwards on Weibo (30分)

1. 题目

1076 Forwards on Weibo (30分)

2. 思路

  1. 利用vector<int> follows[MAXN] 存放节点
  2. 存放为关注我的,而不是我关注的
  3. 使用两个queue,一层层向外,使用visited存储是否被访问过

3. 注意点

  1. MAXN的定义为1001,因为下标从1开始
  2. 每次visited都需要恢复原来状态(全为false,因为系统默认初始化false)

4. 代码

#include<cstdio>
#include<queue>
#include<vector>

#include<iostream> 
using namespace std;

#define MAXN 1001

bool visited[MAXN];
vector<int> follows[MAXN];

int cal(int id, int level){
    int count = 0;
    queue<int> q1;
    queue<int> q2;
    q1.push(id);
    visited[id] = true;
    while(level > 0){
        while(!q1.empty()){
            id = q1.front();
            q1.pop();
            for(int j=0;j<follows[id].size();j++){
                if(visited[follows[id][j]] == false){
                    visited[follows[id][j]] = true;
                    q2.push(follows[id][j]);
                    count++;
                }
            }
        }
        if(q2.size() == 0){
            break;
        }
        q1 = q2;
        queue<int> q3;
        q2 = q3;
        level--;
    }
    return count;
}

int main(){
    int n, level;
    scanf("%d %d", &n, &level);
    int m, id;
    for(int i=1;i<=n;i++){
        scanf("%d", &m);
        for(int j=0;j<m;j++){
            scanf("%d", &id);
            follows[id].push_back(i);
        }
    }
    vector<int> res;
    int num;
    scanf("%d", &num);
    for(int i=0;i<num;i++){
        scanf("%d", &id);
        res.push_back(cal(id, level));
        fill(visited, visited+MAXN, false);
    }
    for(int i=0;i<num;i++){
        printf("%d\n", res[i]);
    }
}
上一篇:PAT 1076 Forwards on Weibo


下一篇:PAT-B 1076 Wifi密码