I am facing problem in this question Little Shino and K Ancestor | Practice Problems.
What I did differently from editorial was just placed that line “ans[color[ele]].pb(ele);” as soon as i enter the dfs function instead of that !visited block. The result should be same with a slight change in base condition that now i have to access"res[ele]=ans[color[ele]][size-k-1];" instead of “res[ele]=ans[color[ele]][size-k];” because now i am inserting earlier as soon as dfs function starts.
The line where you are making mistake is the line to pop element in for loop in the dfs function(Line 34-35).
In Authors solution, we are pushing the element in the for loop and then after the dfs is returned we pop the element. But in your case you are not pushing the element in the for loop, you are just popping the element, which might give you a wrong answer.
The Tester’s solution is quite similar to yours and he is popping the element after the for loop gets terminated whereas you are popping the element within for loop.
Thank you @therisingsun for your fast reply. Yes you are right what question demanded was to pop some element only if all its neighbors are visited and in my code there was a possibility that all neighbors are not visited and i pop that element. So when code reaches last line all neighbors of ele will be visited and we can pop it back.
But still i could not figure any tc where this thing would occur. Don’t know
Actually, the thing is that i would be moving one step back in the case when i pop back inside loop which means that is the element would be popped a step after as compared to the case of popping it outside the loop.
But how does that matter after all i when it reaches to condition if(size>k) in dfs function it will have those vertices which are of same color.
Am i clear in stating my problem if not please let me know. @vijju123 ,@meooow can you please help.
The above link contains the case where your code fails. Dry run your code for the test case given in the above link. You will come to know about the mistake. If you will still have any query, just comment and I will explain the problem in a more descriptive way.
Hey @vishesh_345, @therisingsun is right. Remember that the ele in the next dfs call is not the current ele. Try to debug it, you’re surely understand.
Yes @meooow I got my mistake if i have pushed something then as soon as i return that node should also be removed from stack(vector in this case).
That test was helpful in debugging this.
Thank you @therisingsun, @meooow. Finally an AC
