Editorial for COCI '15 Contest 3 #3 Molekule


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The key observation in this task is to notice that we can always construct the solution so that the longest path an impulse has to travel is 1. Since the graph of molecules is a tree, we can color the molecules in two colors (e.g. black and white) using the DFS algorithm so that there are no two molecules of the same color that are connected with a covalent bond. Now we must direct each covalent bond so that it points from the white molecule to the black one. It is clear that a path longer than 1 does not exist in the newly created graph.

Notice that the claim can be generalized to any bipartite graph.


Comments

There are no comments at the moment.