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 N nodes with M edges, such that there are X SCC's (Strongly Connected Components) on the condition that Q pairs (x_i, y_i) belong to the same SCC.

Consider the edge types for a graph with X SCCs:

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

  • Edges between SCCs. Consider all \binom{X}{2} pairs of SCCs. For an SCC with size \alpha and another with size \beta, \alpha\beta edges can be formed between them.

The next step involves choosing X distinct SCCs:

Subtask 1

Since Q = 0, we pick the X SCCs to to be \{1\}, \{2\}, \dots, \{X-1\}, \{X \dots N\}. 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.

Subtask 2

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

Let sz[i] be the size of the i-th SCC. For the X SCCs considered, each requires a minimum of sz[i] edges to satisfy the properties of an SCC, unless it is a single node. For example, if one set of nodes were \{1, 2, \dots, k\}, the edges formed would be 1 \to 2, 2 \to 3, \dots, k-1 \to k, k \to 1.

If \sum sz[i] > M, there are not enough edges to satisfy the constraint of M edges, so output -1.

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

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

Time Complexity: \mathcal{O}(N + Q \log N + M \log M)


There are no comments at the moment.