1076 forwards on Weibo (30 points)

30min

1076 Forwards on Weibo (30 branch )

The question

Let's give a digraph , Yes n Nodes , For nodes, there are m A asked , Ask this node k The number of nodes that can be reached within a step （ Walking along one side is a step , The distance from this node is no more than k Number of nodes ）.
Yes n That's ok , Each line gives the number i Personal side （ It is someone else who comes to this person's side ）.

Ideas

vector Drawing ,dfs Traverse the queried points , Find a distance of no more than k All nodes of .
Can open an array storage distance .

Be careful vis And order Each iteration must be initialized

Code

#include<stdio.h>
#include<vector>
#include<stack>
#include<string.h>
using namespace std;
vector<int>mp[10007];
int vis[10007],order[10007],k;
int dfs(int x)
{
    
	stack<int>st;
	int next,sum=0;
	memset(vis,0,sizeof(vis));
	memset(order,0,sizeof(order));// Be careful vis  And order Each iteration must be initialized 

	st.push(x);
	vis[x]=1;
	while(!st.empty()){
    
		next=st.top();
		st.pop();
		if(order[next]>=k){
    
			continue;
		}
		for(int i=0;i<mp[next].size();i++){
    
			if(vis[mp[next][i]]==0){
    
				vis[mp[next][i]]=1;
				order[mp[next][i]]=order[next]+1;
				st.push(mp[next][i]);
				sum++;
			}
		}
	}
	return sum;
}
int main()
{
    
	int n,m,x;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
    
		scanf("%d",&m);
		for(int j=0;j<m;j++){
    
			scanf("%d",&x);
			mp[x].push_back(i);
		}
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
    
		scanf("%d",&x);
		printf("%d\n",dfs(x));
	}
	return 0;
}