@vijju123 Sir, this question is from the cook off JAN,2018. I know of graph colouring and dfs concepts but I have absolutely not been able to grasp the way graph colouring is being applied here.
Can you kindly help me out?? Also how should I be able to realize that it can be solved by graph colouring??
Anyone else who understood the solution, I would also request to help me in this problem if you kindly can…
Thanks in advance to all of those who will help me…
I am not really sure how to help you because the entire editorial was about how graph coloring is used.
From a very high abstracted view, we obtained constraints regarding if adjacent nodes can be of same color or not. The constraints are represented by edges in the graph.
At the end, we assign the root node one color, and its adjacent nodes are assigned color based on constraints depicted by edges and so on until entire tree is colored or we get an impossible situation.
1 Like