PAT甲级1076.

目录

A1076

题目

样例

输入:

7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6

输出:

4
5

思路和坑点

　　对查询的结点使用bfs方法，查询层数在规定的L以内的个数，即为所需要的统计结果，当遍历的层数达到要求时要提前终止循环。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1002
vector<int> v[MAXN];
vector<bool> vis(MAXN);
int n,l;
int findans(int s){                         //bfs函数 
    fill(vis.begin(),vis.end(),false);      //访问标记初始化 
    int layer=1,last=s,tail;                //层数，last为当前层的最后一个，tail用于更新last 
    int cnt=0;                              //cnt为计数 
    queue<int> q;
    q.push(s);
    vis[s]=true;
    while(!q.empty()){                      //使用队列进行层序遍历 
        int now=q.front();
        q.pop();
        for(int i=0;i<v[now].size();i++){
            int k=v[now][i];
            if(vis[k]==false){
                q.push(k);
                vis[k]=true;
                cnt++;
                tail=k;
            }    
        }
        if(now==last){                      //如果当前层结束，layer++，如果层数超过规定的l则退出循环 
            layer++;
            if(layer>l) break;
            last=tail;
        }
    }
    return cnt;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++){                //读入数据 
        int num;    scanf("%d",&num);
        for(int j=0;j<num;j++){
            int temp; scanf("%d",&temp);
            v[temp].push_back(i);
        }
    }
    int k;
    scanf("%d",&k);                        //读入查询，并打印结果 
    for(int i=0;i<k;i++){
        int id;        scanf("%d",&id);
        printf("%d\n",findans(id));
    }
    return 0;
}