What do we have to find in this question? maximum no. of edges to be removed or maximum num. of vertices

#1

https://practice.geeksforgeeks.org/problems/divisibility-tree/0

#2

You are supposed to find out maximum no. of edges to be removed such that after removing each connected component has even no of vertices.

#3

Any suggestions on how to approach this.

#4

You can run dfs here and maintain the no of vertices visited so far and a global variable ‘ans’. increment the variable ans each time when no of vertices is even and by this way you will get the answer. This solution works because you can remove the edge after even number of vertices and there is no cycle in the graph so there will be no back edge that to be considered.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.