Fragile | Topcoder Archive

Problem Statement

You are given two ints: N and K. Lun the dog is interested in the undirected graphs that satisfy the following conditions:

The graph has exactly N vertices, labeled from 0 to N-1. Each vertex has a unique label.
The graph has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices.
The graph has exactly K bridges (edges whose deletion increases its number of connected components).

Find and return the number of these graphs modulo 1,000,000,007.

Definition

Class:: Fragile
Method:: countGraphs
Parameters:: int, int
Returns:: int
Method signature:: int countGraphs(int N, int K)
(be sure your method is public)

Notes

Two graphs are considered different if and only if there exists a pair of vertices such that one of the graphs contains an edge between them, and the other does not.

Constraints

N will be between 1 and 50, inclusive.
K will be between 0 and N-1, inclusive.

Examples

```
3
```
```
2
```
```
Returns: 3
```
The following three graphs satisfy the conditions:
```
4
```
```
0
```
```
Returns: 15
```
The following 15 graphs satisfy the conditions:
```
5
```
```
2
```
```
Returns: 195
```
The following is some of the graphs that satisfy the conditions: Here, bridges are painted in brown, and "x n" represents that there are n graphs that are isomorphic to that graph.
```
50
```
```
25
```
```
Returns: 353637389
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.