AcWing 1562. 微博转发(DFS版本)
原题链接
简单
作者:
say1ka
,
2023-03-23 11:53:54
,
所有人可见
,
阅读 176
#include <bits/stdc++.h>
using namespace std;
int n,l;
vector<int> g[1010];
int st[1010];
int dfs(int u,int t)
{
int ans=0;
if(t>l||t>=st[u])return ans;
if(st[u]==0x3f3f3f3f)ans++;
st[u]=t;
for(int i=0;i<g[u].size();i++)
ans+=dfs(g[u][i],t+1);
return ans;
}
int main ()
{
cin>>n>>l;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
for(int j=0;j<x;j++)
{
int y;
cin>>y;
g[y].push_back(i);
}
}
int k;
cin>>k;
for(int i=0;i<k;i++)
{
int x;
cin>>x;
memset(st,0x3f,sizeof st);
cout<<dfs(x,0)-1<<"\n";
}
}
%%% 琢磨了很久为什么st数组不开bool,才发现是因为上一层的粉丝有可能会先被下层调用却不能扩展,太牛了%%%
%%%