Consider a connected component \(G'\) in \(G\). If this graph has \(N'\) vertices, it also has \(N\) edges, so \(G'\) has exactly one cycle.

Therefore, we will count cycles instead of connected components.

First, we count the cycles that exist when we span the edges for such \(i\)’s that \(A_i \neq -1\).

Now, each connected component without a cycle is a tree. We number them \(1,2,\dots,K\) and let \(B_i\) be the size of the connected component numbered \(i\).

For \(1 \le x_1 < x_2 < \dots < x_k \le K\), we find the number of cycles that contain vertices in the connected components numbered \(x_1,x_2,\dots,x_k\), which is \((k-1)! \times \prod_{i=1}^{k} B_{x_i}\).

Therefore, we can find for each \(k\) the sum of \(\prod_{i=1}^{k} B_{x_i}\) with dynamic programming to solve the problem in \(\mathrm{O}(N^2)\) time.

We can also compute \(\prod_{i=1}^{K} (1 + B_ix)\) with divide-and-conquer to solve it in \(\mathrm{O}(N\log^2 N)\) time.