## Editorial for DMOPC '21 Contest 4 P4 - Christmas Graph

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: 4fecta

This subtask was created to reward brute force solutions.

Time Complexity:

There are many possible solutions with quadratic time complexity, of which we present one. First of all, let's direct all the edges added towards the respective randomly chosen nodes, so that the result becomes a functional graph. By linearity of expectation, the expected number of components is equivalent to , where is the expected number of components of size . To compute , assume we know the number of connected functional graphs of size with no self-loops . Then, for any of the sets of nodes, the probability that they form a single component is

because there are ways to have the nodes in the set form a component and total ways to direct edges between the nodes not in the set. So, again by linearity of expectation, can be expressed as

It remains to calculate for all values of . Let's first initialize all to and then subtract away the number of graphs with more than a single component. We now do the subtractions by establishing recursive relations. For any fixed , focus on the component of a single node . If there are nodes in the component of node , then there are ways to choose the nodes in the component of , different ways for them to form a component, and total ways to direct edges between the nodes not in 's component. So, for every from to , we should subtract

from , which concludes the solution.

Time Complexity: