悬关,BFS,不知道哪错了
查看原帖
悬关,BFS,不知道哪错了
981994
xinglili楼主2023/11/4 21:29
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int N=1e5+10;
int n,d,ans;

int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int vis[N];
bool st[N];
void bfs(int x)
{
    queue<int> q;
    q.push(x);
    st[x]=true;
    
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(!st[j])
            {
                st[j]=true;
                vis[j]=vis[t]+1;
                if(vis[j]<=d)
                {
                    ans++;
                    q.push(j);
                }
            }
        }
        
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    cin>>n>>d;
    
    int a,b;
    for(int i=1;i<=n-1;i++)
    {
        cin>>a>>b;
        add(a,b),add(b,a);//无向图
    }
    
    bfs(1);
    cout<<ans;
    
    return 0;
}
2023/11/4 21:29
加载中...