Subtask 1

This subtask was created to reward brute force solutions.

Time Complexity: ~\mathcal{O}(N(N-1)^N)~

Subtask 2

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 ~\sum_{k=2}^N E[k]~, where ~E[k]~ is the expected number of components of size ~k~. To compute ~E[k]~, assume we know the number of connected functional graphs of size ~k~ with no self-loops ~F[k]~. Then, for any of the ~\binom{N}{k}~ sets of ~k~ nodes, the probability that they form a single component is

$$\displaystyle \frac{F[k](N-k-1)^{N-k}}{(N-1)^N}$$

because there are ~F[k]~ ways to have the ~k~ nodes in the set form a component and ~(N-k-1)^{N-k}~ total ways to direct edges between the ~N-k~ nodes not in the set. So, again by linearity of expectation, ~E[k]~ can be expressed as

$$\displaystyle \binom{N}{k}\frac{F[k](N-k-1)^{N-k}}{(N-1)^N}.$$

It remains to calculate ~F[k]~ for all values of ~k~. Let's first initialize all ~F[k]~ to ~(k-1)^k~ 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 ~k~, focus on the component of a single node ~v~. If there are ~i~ nodes in the component of node ~v~, then there are ~\binom{k-1}{i-1}~ ways to choose the nodes in the component of ~v~, ~F[i]~ different ways for them to form a component, and ~(k-i-1)^{k-i}~ total ways to direct edges between the ~k-i~ nodes not in ~v~'s component. So, for every ~i~ from ~2~ to ~k-1~, we should subtract

$$\displaystyle \binom{k-1}{i-1}F[i](k-i-1)^{k-i}$$

from ~F[k]~, which concludes the solution.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 3

It is helpful to note that the number of components in a functional graph is equal to the number of cycles in the graph. We may therefore calculate the expected number of cycles instead. By linearity of expectation, the expected number of cycles is equivalent to ~\sum_{k=2}^N E[k]~, where ~E[k]~ is the expected number of cycles of size ~k~. Note that for any set of ~k~ nodes, the probability that they form a cycle is ~(k-1)!/(N-1)^k~ because there are ~(k-1)!~ cycles of length ~k~ and each of the ~k~ nodes has a ~1/(N-1)~ chance of pointing towards the correct node that comes next in the cycle. So, again by linearity of expectation, ~E[k]~ can be expressed as

$$\displaystyle \binom{N}{k}\frac{(k-1)!}{(N-1)^k}.$$

This can easily be computed in constant time with some precomputation.

Time Complexity: ~\mathcal{O}(N)~