I get it till counting the number of connected components & number of odd degree vertices, but why do we need to take the maximum of (num of components-1) and ((num of odd degree vertices-1)/2) ?
Link to code : https://ide.codingblocks.com/s/263705
(doubt in line 78)
Hey consider this simple case:
although there is only one connected component, still you can’t complete it in one stroke(you need to add atleast one more extra line)
But how does ((num of odd degree vertices-1)/2) gives us the number of extra edges to complete it in one stroke ?
See except for the starting and ending point, all points need to have even degree inorder to complete figure in one stroke(because for every point except start and end, you will go towards it and also leave it) hence if some node has odd degree then eventually you have to reach it by making extra line(note that this extra line again makes the degree of that node even)
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.