C++ BFS Solution O(n)


#1

I created the array A1 to maintain 1 based indexing everywhere. It is not necessary though.

    int Solution::solve(vector<int> &A, vector<vector<int> > &B, int C) {
        vector<int> A1;
        if(A.size()==1){
            if(C>=1)
                return 1;
            return 0;
        }
        if(A.size()==0)
            return 0;
        A1.push_back(0);
        for(int i = 0; i<A.size(); i++)
            A1.push_back(A[i]);
        vector<int> graph[A.size()+1];
        for(int i = 0; i<B.size(); i++){
            graph[B[i][0]].push_back(B[i][1]);
            graph[B[i][1]].push_back(B[i][0]);
        }
        vector<int> vis(A.size()+1, 0);
        queue<pair<int,int>> q;
        int go = 0;
        if(A1[1]==1)
            go++;
        q.push({1, go});
        int ans = 0;
        vis[1]++;
        while(q.size()){
            pair<int,int> pr = q.front();
            q.pop();
            int curr = pr.first;
            int till = pr.second;
            if(graph[curr].size()==1 && till<=C){
                ans++;
                continue;
            }
            for(int i = 0; i<graph[curr].size(); i++){
                int node= graph[curr][i];
                if(vis[node]==0){
                    int go1 = till+A1[node];
                    vis[node]++;
                    q.push({node, go1});
                }
            }
            
        }
        return ans;
    }