Problem Statement
You are given two
- 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
1
0
Returns: 1
2
0
Returns: 1
2
1
Returns: 1
3
0
Returns: 2
3
1
Returns: 3
4
1
Returns: 18
4
2
Returns: 15
4
3
Returns: 16
5
0
Returns: 314
5
1
Returns: 280
5
3
Returns: 110
5
4
Returns: 125
6
4
Returns: 1080
7
0
Returns: 1137508
8
2
Returns: 18308934
9
5
Returns: 42022260
10
8
Returns: 72000000
11
1
Returns: 596858841
12
2
Returns: 648619755
13
7
Returns: 53045030
14
13
Returns: 911978445
15
13
Returns: 102427527
16
3
Returns: 702517171
17
1
Returns: 31503346
18
6
Returns: 832562047
19
2
Returns: 302707424
20
10
Returns: 396354053
21
7
Returns: 3170380
22
15
Returns: 606721239
23
2
Returns: 35748661
24
8
Returns: 275833657
25
3
Returns: 344304028
26
15
Returns: 114450856
27
20
Returns: 60932377
28
6
Returns: 109197205
29
8
Returns: 29187184
30
12
Returns: 225754637
31
18
Returns: 752869846
32
19
Returns: 462258971
33
29
Returns: 740600360
34
31
Returns: 926274464
35
21
Returns: 828970495
36
34
Returns: 843527236
37
36
Returns: 846631831
38
23
Returns: 732726723
39
29
Returns: 558946916
40
15
Returns: 661614094
41
24
Returns: 305099601
42
29
Returns: 660679771
43
31
Returns: 807613155
44
43
Returns: 962074526
45
29
Returns: 500950647
46
43
Returns: 41018650
47
13
Returns: 782846135
48
18
Returns: 435389744
49
47
Returns: 804214110
50
0
Returns: 817615391
50
1
Returns: 391592736
50
2
Returns: 955227149
50
3
Returns: 213215122
50
4
Returns: 611920316
50
5
Returns: 981351269
50
6
Returns: 11359946
50
7
Returns: 267633299
50
8
Returns: 135761627
50
9
Returns: 247379320
50
10
Returns: 827473297
50
11
Returns: 615946594
50
12
Returns: 792281627
50
13
Returns: 420918692
50
14
Returns: 572233733
50
15
Returns: 666287965
50
16
Returns: 693926056
50
17
Returns: 826973602
50
18
Returns: 54192294
50
19
Returns: 334190416
50
20
Returns: 474781000
50
21
Returns: 89175524
50
22
Returns: 352233811
50
23
Returns: 943967764
50
24
Returns: 467827283
50
26
Returns: 678932015
50
27
Returns: 382760017
50
28
Returns: 480947388
50
29
Returns: 732741129
50
30
Returns: 877378704
50
31
Returns: 35671553
50
32
Returns: 244804576
50
33
Returns: 432922757
50
34
Returns: 417165837
50
35
Returns: 954080251
50
36
Returns: 237524660
50
37
Returns: 663225573
50
38
Returns: 918726516
50
39
Returns: 414379904
50
40
Returns: 211599682
50
41
Returns: 165808983
50
42
Returns: 277568899
50
43
Returns: 112134236
50
44
Returns: 161477050
50
45
Returns: 774268943
50
46
Returns: 401948922
50
47
Returns: 825238479
50
48
Returns: 384983970
50
49
Returns: 48440174