FillInTheGraph | Topcoder Archive

Problem Statement

This problem has a non-standard time limit: 4 seconds.

You are given a directed graph with n nodes and m edges. The i-th edge goes from node a[i] to b[i]. Find the numbers of ways to complete the following task:

Choose a number k between 1 and n, inclusive.
Label each node in the graph with a number between 1 and k, inclusive.
For each j from 1 to k-1, inclusive, there must exist an edge from a node with label j to a node with label j+1.

Two ways to complete the task are different if there exists a node that ends up with a different label.

Return the number of ways, modulo 10^9+7.

Definition

Class:: FillInTheGraph
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.
a will have between 1 and n*(n-1) elements, inclusive.
a and b will have the same length.
For all valid i, a[i] != b[i].
All ordered pairs (a[i],b[i]) will be distinct.

Examples

```
3
```
```
{0,1,2}
```
```
{1,2,0}
```
```
Returns: 10
```
In this case, there are 10 valid colorings [1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,2,2], [2,1,2], [2,2,1], [1,2,3], [2,3,1], [3,1,2]
```
5
```
```
{0,1,2}
```
```
{1,2,0}
```
```
Returns: 52
```
Note that the graph can be disconnected
```
2
```
```
{}
```
```
{}
```
```
Returns: 1
```
```
3
```
```
{2,1,0,1,2}
```
```
{1,0,1,2,0}
```
```
Returns: 11
```

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

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

Returns: 830203593

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.