BFS CPP solution


#1

int Solution::solve(vector &A, vector<vector > &B, int C) {

vector<vector<int> > adj(A.size()+1);
for(int i=0;i<B.size();i++){
    adj[B[i][0]].push_back(B[i][1]);
    adj[B[i][1]].push_back(B[i][0]);
}
vector<bool> visited(A.size()+1);
vector<int> good(A.size()+1,0);
int ans = 0;
good[1] = A[0];
queue<int> q;
q.push(1);
while(!q.empty()){
    int node = q.front();
    q.pop();
    visited[node]=true;
    int previousSize = q.size();
    for(auto j : adj[node]){
        if(!visited[j])q.push(j);
        good[j]=good[node]+A[j-1];
    }
    if(previousSize == q.size() and good[node]<=C)ans++;
}
return ans;

}


#2
previousSize == q.size()
You Use this condition to check whether this node is leaf or not....Right?

#3

Yes, no change in the size of q implies that it is a leaf node.