I am trying to submit almost identical code(Beautiful Graphs from codeforces discussed in Graph-10 Competitive Problems), but getting Wrong Answer. The question has been solved in C++ in the video but I solve the problems in Java and I am unable to understand what changes should be made if it is because of language.
My code is pasted here: https://pastebin.com/Jp7FUbie
Please have a look because I am unable to solve problems even after understanding the concepts and code.
Hi I looked at your java code and found that it is not using the same algorithm as the C++ solution illustrated in the video. Specifically the dfs part is different in your code compared to the solution where the java code is using a graph coloring method while the C++ code is using a parity based method. The drawback in the coloring method is that the two groups (even and odd) cannot be reacted to in different methods whereas it can be in the parity one.
More simply, graph coloring is taking both even and odd as equivalent groups( i.e 50% chances to both) where this is not the case due to 2 odd numbers(1 and 3) being present while only 1 even(2) is there. This is handled by assigning different parities to the groups as 2 and 1 respectively.
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.