AcWing
1562. 微博转发
基于邻接表的BFS(时间复杂度$O(V+E)$，如果使用临界矩阵，时间复杂度为$O(V^2)$)，使用lev数组记录层数。注意每次查询之前清空visited数组和lev数组(从1开始编号)。
#include <bits/stdc++.h>
using namespace std;
int n, l, m, k;
const int N = 1010;
vector<vector<int> > adl;
int visited[N], lev[N];
int main(){
cin >> n >> l;
adl.resize(n + 1);
for(int i = 1; i <= n; i++){
int temp;
cin >> m;
while(m--){
cin >> temp;
adl[temp].push_back(i);
}
}
cin >> k;
while(k--){
fill(visited + 1, visited + n + 1, 0);
fill(lev + 1, lev + n + 1, 0);
queue<int> q;
int temp;
cin >> temp;
q.push(temp);
visited[temp] = 1;
while(!q.empty()){
int top = q.front();
q.pop();
for(auto i : adl[top]){
if(!visited[i]){
visited[i] = 1;
lev[i] = lev[top] + 1;
q.push(i);
}
}
}
int cnt = 0;
for(int i = 1; i <= n; i++) if(lev[i] <= l && lev[i] != 0) cnt++;
cout << cnt << endl;
}
return 0;
}