图论 BFS
从起点开始进行bfs,搜索深度为l层,统计 l层中不同节点个数
1000 1000 1000 (询问次数) ∗ 1000 ∗ 100 * 1000*100 ∗1000∗100 (每次bfs需要搜索的边数) = 1 0 8 = 10^8 =108
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
#define int long long
#define x first
#define y second
#define ump unordered_map
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pair PII;
const int N=1005, M=100005;
int n, l, m, us, k, kk;
int ne[M], h[N], e[M], idx;
bool st[N];
//int t, n, m, cnt, ans;
inline int rd(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
void add(int a, int b){
e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
int dfs(int S){
int ans=0;
queue q;
memset(st, 0, sizeof st);
q.push(S);
st[S]=true;
rep(i, 0, l){
int sz=q.size();
ans+=sz;
rep(j, 0, sz){
int mm=q.front();
q.pop();
for(int o=h[mm]; ~o; o=ne[o]){
int p=e[o];
if(!st[p]){
st[p]=true;
q.push(p);
}
}
}
}
return ans+q.size()-1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n=rd(), l=rd();
memset(h, -1, sizeof h);
rep(i, 1, n+1){
m=rd();
while(m--){
us=rd();
add(us, i);
}
}
k=rd();
while(k--){
kk=rd();
printf("%lld\n", dfs(kk));
}
return 0;
}
AcWing 1562. 微博转发(PAT甲级辅导课)y总视频讲解
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈