分析:BFS的使用,若用DFS会漏掉许多情况,比较麻烦。
#include <iostream>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<iostream>
using namespace std;
#define MAX 999999999
int n,m,k,ds;
struct Node{
vector<int>user;
int layer;
};
int visi[10001];
int cnt;
Node node[10001];
void bfs(int root)
{
queue<int>q;
q.push(root);
visi[root] = 1;
while(!q.empty())
{
int fro = q.front();
for(int i = 0; i < node[fro].user.size(); i++)
if(!visi[node[fro].user[i]] && node[fro].layer < k){
node[node[fro].user[i]].layer = node[fro].layer + 1;
q.push(node[fro].user[i]);
visi[node[fro].user[i]] = 1;
cnt ++;
}
q.pop();
}
}
int main()
{
cin>>n>>k;
for(int i = 1; i <= n; i++)
{
int p;cin>>p;
for(int j = 1;j <= p ;j++)
{
int x;
cin>>x;
node[x].user.push_back(i);
}
}
cin>>m;
for(int i = 0; i < m; i++)
{
int x;cin>>x;
cnt = 0;
node[x].layer = 0;
memset(visi, 0 , sizeof(visi));
bfs(x);
cout<<cnt<<endl;
}
return 0;
}