Editorial for COCI '21 Contest 6 #3 Naboj


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 metal balls from the problem can be thought of as nodes of a graph, and the copper wires can be thought of as edges. When the professor charges a ball, this now corresponds to directing all the edges either towards that node or away from it. The problem now boils down to checking whether it is possible to obtain the desired directed graph starting from a given undirected graph using such operations.

Let's look at what happens if the graph contains a directed cycle. Assume that there exists a solution, i.e. a sequence of moves which obtains the desired graph. Suppose d is the index of the last node in the cycle which has been charged. Then, all of the edges from the cycle connected to this node d would have to point either towards d or away from it, which is impossible since there should be an edge both entering and exiting it. Therefore, if the final directed graph contains a cycle, then the answer is -1 and it is not possible to obtain the desired directions.

We can check whether there is a directed cycle using a DFS traversal of the graph. If the graph doesn't contain a cycle, we can do a topological sort on the nodes. If we iterate over the nodes in this order, since there are no cycles, we can find a simple sequence of moves. Just charge the nodes in the order of the topological sort.


Comments

There are no comments at the moment.