Editorial for An Animal Contest 4 P5 - Neighbourly Neighbourhoods

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: sjay05

In summary, this problem asks us to construct a directed graph of nodes with edges, such that there are SCC's (Strongly Connected Components) on the condition that pairs belong to the same SCC.

Consider the edge types for a graph with SCCs:

• Edges within an SCC. For an SCC consisting of nodes (size ), there are a maximum of possible edges that can be formed.

• Edges between SCCs. Consider all pairs of SCCs. For an SCC with size and another with size , edges can be formed between them.

The next step involves choosing distinct SCCs:

Since , we pick the SCCs to to be . The size of the last SCC needs to be maximized, to maximize the number of edges that can be placed on the first condition listed above.

Let be the maximum number of SCCs that can be created from the input. This can be finding the number of connected components of the constraints with a DSU. If , output -1. If , the largest components (by size) must be considered as 1 SCC, to total SCCs. The "largest" are being considered to maximize the number of edges to be placed on the first condition listed above.

Let be the size of the -th SCC. For the SCCs considered, each requires a minimum of edges to satisfy the properties of an SCC, unless it is a single node. For example, if one set of nodes were , the edges formed would be .

If , there are not enough edges to satisfy the constraint of edges, so output -1.

Finally if , for each SCC with size you can add more edges, and add edges between SCCs. Note that when constructing edges between SCCs, for each pair of SCCs (suppose SCC and SCC ), edges must only flow from a node in to a node in , or vice versa. Accounting for both directions will unite and as 1 SCC, which needs to be avoided.

At this point, if we have already reached our required edges, we can simply output them and terminate our program. If is still greater than the number of possible edges that can be added, output -1.

Time Complexity: