大致思路:题目给出了明显的层次关系,显然是让我们用BFS去搜索,在定义一个数组 level
用来记录每一个结点坐在的层数 level[子节点] = level[父节点] + 1
。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<vector<int>> graph;
int n, l, k;
int level[N];
bool vis[N];
inline int BFS(int st) {
memset(vis, 0, sizeof(vis));
queue<int> q;
q.push(st);
vis[st] = true;
level[st] = 0;
int cnt = -1; //第一层不计算在内
while(!q.empty()) {
int t = q.front(); q.pop();
if (level[t] > l) break;
cnt++;
for (int i = 0; i < graph[t].size(); i++) {
int tmp = graph[t][i];
if (!vis[tmp]) {
vis[tmp] = true;
level[tmp] = level[t] + 1;
q.push(tmp);
}
}
}
return cnt;
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &l);
graph.resize(n + 1);
for (int i = 1; i <= n; i++) {
int m; scanf("%d", &m);
while(m--) {
int x; scanf("%d",&x);
graph[x].push_back(i);
}
}
scanf("%d", &k);
while(k--) {
int q; scanf("%d",&q);
int ans = BFS(q);
printf("%d\n", ans);
}
return 0;
}