C++ Dfs Solution by counting the number of nodes which have subtrees with even nodes


#1

int dfsCount(vector adj[],int i, unordered_map<int,int> &count,vector &visited){
visited[i]=1;
count[i]=1;
for(auto j=adj[i].begin();j!=adj[i].end();j++){
if(!visited[*j]){
count[i]+=dfsCount(adj,*j,count,visited);
}
}
return count[i];
}
int Solution::solve(int A, vector<vector > &B) {
if(A%2!=0)
return 0;
vector adj[A];
for(int i=0;i<B.size();i++){
adj[B[i][0]-1].push_back(B[i][1]-1);
adj[B[i][1]-1].push_back(B[i][0]-1);
}
unordered_map<int,int> count;
vector visited(A,0);
dfsCount(adj,0,count,visited);
int result=0;
for(auto i=count.begin();i!=count.end();i++){
if((i->second) %2==0)
result++;
}
return result-1;
}