Connection Status:
Competition Arena > StronglyConnectedGraph

StronglyConnectedGraph

2017 TCO Semi 1 · 2017-03-31 · by lg5293

2017 TCO Semi 1 · 2017-03-31 · by lg5293 · Dynamic Programming
Class Name: StronglyConnectedGraph
Return Type: int
Method Name: count
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

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

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

1)
3
{1,2,1,2,1,2}
{2,1,2,1,2,1}
Returns: 0

The graph is not connected.

2)
4
{0,0,1,3,3,2}
{1,2,2,1,2,1}
Returns: 14
3)
2
{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.

4)
15
{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

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

Coding Area

Language: C++17 · define a public class StronglyConnectedGraph with a public method int count(int n, vector<int> a, vector<int> b) · 128 test cases · 2 s / 256 MB per case

Submitting as anonymous