## Editorial for DMOPC '22 Contest 1 P3 - Group Project

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.

Author: Riolku

We have a definition from the statement that works on the graph, but not the one in the input. Try to find an equivalent characterization for the complement graph (the one in the input).

Try drawing a complete graph of size and remove edges until there are no friend groups.

If there is a node in the complement graph with at least two neighbours, and one of the neighbours has at least two neighbours, there is no friend group. Suppose is the other neighbour of , and let be the other neighbour of . If , our group of four is , where is any other node. If , our group of four is .

Implementing this gives us an algorithm.

Nothing particularly new needs to be done, all that needs to be done is figuring out how to maintain the information dynamically.

Call a node heavy if it has at least two neighbours. Maintain the set of heavy nodes, along with another set.