You are supposed to count the number of connected undirected labeled graphs with vertices.
Algorithms with time complexity are preferable.
A Dynamic-Programming Algorithm
Let be the answer for .
The first idea to compute is subtracting the number of disconnected graphs from the total number.
The total number of size- graphs is .
How to count the disconnected graphs?
Let’s consider the size of the connected component containing the vertex labeled with 1.
Since the graph is disconnected, cannot be .
Then the number of disconnected graphs where the connected component containing vertex 1 is a certain one with size is exactly .
Now we have an -time dynamic-programming algorithm as follows.
Expression Rearrangement
If we unfold the binomial coefficients, we will have
Let and .
Moreover, let’s set to and then we have
Note that we already have a convolution-like term in the formula.
An Optimization Based on FFT
We will use Fast Fourier transform (FFT) as an -time algorithm to compute convolution of length .
First of all, are easy to compute so we can pre-process them.
Now we are going to use a divide-and-conquer scheme.
Let be a procedure that computes for all .
In addition, we add the following invariant to this procedure:
When invoking , we already compute for each , the partial convolution , and store them in .
Then our algorithm proceeds as follows.
If , we set to .
Otherwise, let’s invoke first where , i.e., the middle point.
Now we already solve the first half of the problem.
To become able to invoke to complete the second half, we need to do something to maintain the invariant above.
In essence, we need to update
for each .
Here comes the chance for optimization.
What we really want to compute is the convolution of and !
Let the convolution result be and indeed we have
for each .
After performing for each , we reestablish the invariant and we can recurse to .
Finally, let’s estimate the time complexity of the algorithm above.
Let be the running time of with .
By using FFT to compute the convolution, we can establish the following
Then by the Master Theorem we derive that .
What’s More
For those who could read Chinese, CDQ’s divide-and-conquer is a good reference about applications of the divide-and-conquer scheme in this post.