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)\).