HDU 4707 Pet （热身赛其次题）

HDU 4707 Pet （热身赛第二题）

转载请注明出处：http://blog.****.net/a1dark

分析：读懂题意之后很简单的一个搜索、在D之外的个数有多少个、

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
struct node{
    int s,e;
    int next;
}cnt[100005*4];
int root[100005];
int vis[100005];
int dis[100005];
int ans,n,num,T;
void add(int s,int e){
    cnt[++ans].e=e;
    cnt[ans].next=root[s];
    root[s]=ans;
}
void bfs(){
    queue<int>q;
    q.push(0);
    vis[0]=1;
    dis[0]=1;
    int s,e,i;
    while(!q.empty()){
        s=q.front();
        if(dis[s]==T+2)
            break;
        q.pop();
        for(i=root[s];i!=-1;i=cnt[i].next){
            e=cnt[i].e;
            if(!vis[e]){
                vis[e]=1;
                dis[e]=dis[s]+1;
                q.push(e);
            }
        }
    }
    for(i=0;i<n;i++){
        if(dis[i]==T+2 || dis[i]==0)
            num++;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        num=0;
        memset(root,-1,sizeof(root));
        memset(vis,0,sizeof(vis));
        memset(dis,0,sizeof(dis));
        ans=-1;
        scanf("%d%d",&n,&T);
        for(int i=0;i<n-1;i++){
            int s,e;
            scanf("%d%d",&s,&e);
            add(s,e);
        }
        bfs();
        printf("%d\n",num);
    }
    return 0;
}