StronglyConnectedGraph | Topcoder Archive

Problem Statement

Note: This problem has a nonstandard time limit: 3 seconds.

A directed graph is called strongly connected if, for each pair of nodes u and v, there is both a directed path from u to v and a directed path from v to u.

You have an undirected graph with n nodes, numbered 0 through n-1, and m edges, numbered 0 through m-1.

You are given the int n. You are also given the int[]s a and b with m elements each. These describe the edges of your graph: for each valid i, edge number i connects the vertices a[i] and b[i]. Each pair of vertices may be connected by arbitrarily many edges. There will be no self-loops: a[i] will never be equal to b[i].

You want to change your graph into a directed graph by assigning one of the two possible directions to each edge of your graph. Moreover, you want to do this in such a way that the resulting graph will be strongly connected. Let X be the number of ways to do so. Compute and return the value X modulo (10^9 + 7).

Definition

Class:: StronglyConnectedGraph
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 2 and 15, inclusive.
m will be between 1 and 2,500, inclusive.
a, b will have exactly m elements each.
Each element of a, b will be between 0 and n-1, inclusive.
a[i] != b[i] for all valid i.

Examples

```
5
```
```
{0,1,2,3,4}
```
```
{1,2,3,4,0}
```
```
Returns: 2
```
This is a cycle. There are two ways to orient this cycle.
```
3
```
```
{1,2,1,2,1,2}
```
```
{2,1,2,1,2,1}
```
```
Returns: 0
```
The graph is not connected.
```
4
```
```
{0,0,1,3,3,2}
```
```
{1,2,2,1,2,1}
```
```
Returns: 14
```

{0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,
0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0}

{1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,
1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1}

Returns: 438952511

Don't forget about the mod.

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

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

Returns: 122355627

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.