Editorial for COCI '14 Contest 1 #4 Mafija

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.

A greedy algorithm works in this task: if there is a person X whom nobody has accused, we can declare that person as a mobster. If that person accused person Y, then person Y cannot be declared as a mobster and that person can be removed completely too. When removing person Y, we need to decrease the count of times person Z has been accused, so that person Z can eventually be declared as a mobster.

After repeating this procedure as much as we can, we will end up with cycles. In other words, there won't be a person that hasn't been accused. Then any person can be declared as a civilian and removed, so we can apply the aforementioned procedure again and so on, until there are any unmarked persons left.

Readers that are well informed about graphs will notice that the task is basically finding a maximum independent set on a pseudoforest. It pays off to choose leaves, delete their neighbours and repeating the procedure until there are cycles left (although solvable). This solution is completely equivalent to the previous one, but is easier to visualize.

Both cases need to be implemented carefully so the complexity of the algorithm is \mathcal O(N).


There are no comments at the moment.