Connection Status:
Competition Arena > Fragile

Fragile

SRM 648 · 2015-01-29 · by evima

SRM 648 · 2015-01-29 · by evima · Dynamic Programming, Graph Theory
Class Name: Fragile
Return Type: int
Method Name: countGraphs
Arg Types: (int, int)
Problem Statement

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.

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
0)
3
2
Returns: 3

The following three graphs satisfy the conditions:

1)
4
0
Returns: 15

The following 15 graphs satisfy the conditions:

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

3)
50
25
Returns: 353637389
4)
1
0
Returns: 1

Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Fragile with a public method int countGraphs(int N, int K) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous