Easy cpp O(n) solution


#1

int helper(vector<vector> &g,int cur,vector &vis,int &ans)
{
vis[cur]=1;
int curcom=0;
for(int i=0;i<g[cur].size();i++)
{
int k=g[cur][i];
if(vis[k]==0)
{
int subcom=helper(g,k,vis,ans);
if(subcom%2==0)
ans++;
else
curcom=curcom+subcom;
}
}
return curcom+1;
}
int Solution::solve(int A, vector<vector > &B) {
vector<vector> g(A+1);
for(int i=0;i<B.size();i++)
{
g[B[i][0]].push_back(B[i][1]);
g[B[i][1]].push_back(B[i][0]);
}
int ans=0;
vector vis(A+1,0);
helper(g,1,vis,ans);
return ans;
}