Easy C++ Dfs approch || O(n) time


#1
void dfs(int st,vector<int> &vis,vector<int> &count,vector<int> adj[])
{
    vis[st]=1;
    
    for(auto it: adj[st])
    {
        if(!vis[it])
        {
       dfs(it,vis,count,adj);
           count[st]+=count[it]+1;
        }
    }
    count[st]+=0;
  
}


int Solution::solve(int A, vector<vector<int> > &B) {
    vector<int> 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);
        
    }
    vector<int> count(A,0);
    vector<int> vis(A,0);
    int res=0;
    dfs(0,vis,count,adj);
    
    for(int it=0;it<A;it++)
    {
        if(count[it]%2!=0 && it!=0)res++;
    }
    
    return res; 
}

#2

can you explain the count part in dfs function , how it is working


#3

I have just observed that it can only be fragmented when total nodes below( basically childrens) are odd in number.
just go through two-three examples and you will get it what i am trying to say.
for any help feel free to contact.