- it
- ## PAT A1076
PAT A1076 图的遍历
#include <bits/stdc++.h>
using namespace std
;
struct node
{
int data
;
int layer
;
};
vector
<node
> m
[1010];
bool vis
[1010]={false};
int n
,L
,x
;
int bfs()
{
int cnt
=0;
node now
;
now
.data
=x
;
now
.layer
=0;
queue
<node
> q
;
q
.push(now
);
vis
[now
.data
]=true;
while(!q
.empty())
{
node a
=q
.front();q
.pop();
int v
=a
.data
;int la
=a
.layer
;
for(int i
=0;i
<m
[v
].size();i
++)
{
m
[v
][i
].layer
=la
+1;
if(vis
[m
[v
][i
].data
]==false&&m
[v
][i
].layer
<=L
)
{
q
.push(m
[v
][i
]);
vis
[m
[v
][i
].data
]=true;
cnt
++;
}
}
}
return cnt
;
}
int main()
{
cin
>>n
>>L
;
for(int i
=1;i
<=n
;i
++)
{
node tp
;
tp
.data
=i
;
int k
,a
;cin
>>k
;
while(k
--)
{
cin
>>a
;
m
[a
].push_back(tp
);
}
}
int q
;cin
>>q
;
while(q
--)
{
cin
>>x
;
memset(vis
,false,sizeof(vis
));
int ans
=bfs();
cout
<<ans
<<endl
;
}
return 0;
}
