SpanningSubgraphs | Topcoder Archive

Problem Statement

You are given an undirected graph with n nodes and m edges. The nodes are numbered 0 through n-1. The edges are given in the int[]s a and b: for each valid index i, there is an edge between a[i] and b[i]. This graph may have self-loops or multiple edges.

Let f(k) denote the number of ways to choose a subset of exactly k edges so the graph consisting of all n nodes and the edges you selected is connected. Let g(k) = f(k) modulo (10^9 + 7).

Return a int[] with exactly m-n+2 elements. For each i starting from 0, element i of the return value should be g(i+n-1).

Definition

Class:: SpanningSubgraphs
Method:: count
Parameters:: int, int[], int[]
Returns:: int[]
Method signature:: int[] count(int n, int[] a, int[] b)
(be sure your method is public)

Constraints

n will be between 1 and 15, inclusive.
m will be between n-1 and 200, inclusive.
a and b will contain exactly m elements each.
Each element of a and b will be between 0 and n-1, inclusive.

Examples

```
3
```
```
{0,1,2}
```
```
{1,2,0}
```
```
Returns: {3, 1 }
```
This case is a triangle graph. For k=2, we can choose any subset of 2 edges, for a total of 3 choices. For k=3, we only have one way (choosing all edges).
```
5
```
```
{0,1,4,3}
```
```
{0,1,4,3}
```
```
Returns: {0 }
```
Even though m is at least n-1, the graph you are given is not necessarily connected.

{0,1,1,2,2,2,3,3,4}

{1,2,3,3,4,5,4,5,5}

Returns: {40, 48, 27, 8, 1 }

{7,3,8,2,5,8,5,11,8,3,10,8,6,6,8,8,3,9,4,6,4,6,1,1,5,4,
0,9,4,7,6,0,6,2,2,6,11,4,6,10,9,2,6,0,4,7,6,8,1,3,11,3,
4,8,1,0,12,9,5,14,0,13,7,14,7,9,6,7,8,8,8,4,14,1,13,5,
1,6,13,14,0,4,8,5,13,7,2,10,10,11,8,2,4,13,12,10,5,13,
5,9,6,4,1,11,4,13,6,4,8,8,11,1,14,10,3,1,2,0,10,5,9,5,
10,8,4,2,5,12,7,2,3,2,4,6,9,3,7,9,2,14,14,0,14,3,12,12,
0,11,7,8,6,6,0,10,7,2,0,7,8,10,3,11,11,7,0,0,11,8,6,11,
13,4,11,11,8,5,13,11,9,14,10,1,12,12,3,3,0,13,13,6,2,9,
1,4,2,7,14,5}

{12,8,1,11,1,6,12,3,7,5,1,1,11,11,9,0,7,9,12,8,13,13,11,
0,2,14,12,12,13,10,13,12,2,14,11,13,14,3,12,14,11,5,3,0,
9,0,1,10,5,11,6,6,1,4,0,12,13,1,4,10,9,8,3,4,13,3,10,7,
3,2,13,0,1,13,7,3,3,9,9,10,9,9,0,13,12,3,14,4,1,7,5,0,0,
11,13,0,0,14,13,5,5,0,10,0,3,8,13,4,6,7,4,0,6,7,8,10,7,
4,6,13,0,6,3,2,11,8,7,12,0,14,12,6,10,8,6,9,2,4,14,9,4,
6,3,11,12,8,7,12,14,0,10,11,9,7,4,6,12,13,7,4,13,9,7,13,
2,4,7,6,2,0,10,7,8,13,1,14,13,3,12,14,2,4,6,7,10,11,8,4,
10,13,14,9,0,5,3,0,7,11}

Returns: {165676111, 472152904, 401323420, 92841577, 361806106, 251066093, 860026758, 204774808, 800204699, 78217142, 290847617, 377659363, 799299488, 639266686, 463155556, 542289798, 505455263, 931966095, 332452321, 157494446, 701362585, 4372546, 189983818, 137009880, 456907012, 699388046, 492757156, 402334178, 262521060, 683669243, 218329042, 912344074, 469164876, 951780423, 845657616, 358560958, 877409160, 936645440, 506542339, 711561307, 182417811, 411559656, 609363889, 410499565, 523968597, 808436626, 796861282, 799905851, 332114660, 28142829, 832046308, 515892527, 461122988, 459763203, 639481498, 760842951, 53778152, 531539556, 499281391, 756160187, 408189379, 536177501, 236162240, 932086574, 249801471, 691291871, 305954956, 944526707, 689056121, 509929491, 860012851, 270237338, 530915439, 636690481, 284974622, 213167754, 791793494, 581854637, 515718421, 142304792, 170068497, 175763828, 669814256, 87330307, 657451539, 902803718, 994244944, 710593682, 158314930, 728217704, 428356628, 680806591, 426349961, 578797504, 448716917, 937968991, 727251530, 565010419, 762565871, 373908747, 569188731, 954967822, 83820159, 869337563, 549355611, 927598978, 992408503, 670497964, 348959921, 892858049, 328944072, 946559373, 830835081, 805632932, 389521576, 995252131, 717245242, 882920285, 127735960, 774020953, 299323686, 248711270, 707972648, 824068405, 929290955, 262377161, 603969848, 20319782, 655428762, 772441022, 315946694, 773490199, 63054183, 280718941, 320481045, 714052434, 119312921, 334810041, 844617606, 239955633, 647743078, 159621066, 358764917, 571545322, 29056136, 300270686, 822798951, 841318305, 809733973, 849084831, 542304340, 360014205, 268267900, 461637720, 441483501, 500466014, 722102413, 274028790, 889071123, 456597703, 989359978, 781914152, 339994675, 176509460, 71482668, 940949411, 727100238, 343026545, 279293690, 51741525, 759652847, 198027784, 293410546, 430593193, 339024072, 605239373, 602353448, 433606430, 526225238, 410141720, 62117055, 1274196, 19503, 198, 1 }

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.