1. 题目
2. 思路
- 利用
vector<int> follows[MAXN]
存放节点
- 存放为关注我的,而不是我关注的
- 使用两个queue,一层层向外,使用visited存储是否被访问过
3. 注意点
- MAXN的定义为1001,因为下标从1开始
- 每次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]);
}
}