Contest Duration: - (local time) (100 minutes) Back to Home
Official

## F - Unbranched Editorial by evima

By the requirements that there is no self-loop and the degree of every vertex is at most $$2$$, each connected component are either a path (including an isolated vertex) or a cycle.

The number of graphs whose the maximum size of connected components is $$L$$ is equal to the number of graphs whose the maximum size of connected components is at most $$L$$ subtracted by that of at most $$L-1$$. Now let us consider the number of graphs whose the maximum size of connected components is at most $$S$$.

We use Dynamic Programming. We determine the connected component which each vertex belongs to, in the increasing order of the vertex’s index. Let $$DP[vcnt][ecnt]:=$$ the total number of subgraphs induced by the first $$vcnt$$ vertices, such that the connected components which each of those $$vcnt$$ vertices belongs to has already determined, and $$ecnt$$ edges have been used so far. Let $$x$$ be the minimum index of vertex whose connected component has not yet be determined, and let us consider the transition by determining the connected component $$x$$ belongs to.

• When $$1 \leq S$$ and $$x$$ is an isolated vertex

The number of $$x$$’s component is $$1$$.

The transition is $$DP[vcnt+1][ecnt]+=DP[vcnt][ecnt]$$.

• When $$x$$ belongs to a path consisting of $$k(2 \leq k \leq S)$$ vertices

The number of $$x$$’s component is, $$C(N - vcnt - 1, k-1)$$ for vertices and $$k! / 2$$ for edges.

The transition is $$DP[vcnt+k][ecnt+k-1]+=DP[vcnt][ecnt] \times C(N-vcnt-1,k-1) \times k!/2$$.

• When $$2 \leq S$$ and $$x$$ belongs to a cycle consisting of $$2$$ vertices

The number of $$x$$’s component is, $$N-vcnt-1$$ for vertices and $$1$$ for edges.

The transition is $$DP[vcnt+2][ecnt+2]+=DP[vcnt][ecnt] \times (N-vcnt-1)$$.

• When $$x$$ belongs to a cycle consisting of $$k(3 \leq k \leq S)$$ vertices

The number of $$x$$’s component is, $$CCN-vcnt-1, k-1)$$ for vertices and $$(k-1)!/2$$ for edges.

The transition is $$DP[vcnt+k][ecnt+k]+=DP[vcnt][ecnt] \times C(N-vcnt-1,k-1) \times (k-1)!/2$$.

Here, $$C(n,k)$$ denote the binomial coefficients, which is precalculated using inverse tables or DP. The total time complexity is $$O(NML)$$.

posted:
last update: