DFSCount | Topcoder Archive

Problem Statement

Fox Ciel has a simple undirected graph with n vertices. The vertices are numbered 0 through n-1. The graph is connected.
You are given a String[] G containing the adjacency matrix of the graph. More precisely, for each i and j, G[i][j] is 'Y' if there is an edge between vertices i and j and it is 'N' if there is no such edge.

Ciel then implemented a depth-first search:

p = []

dfs(current) := 
	p.append(current)
	Let adjs[] = list of vertices that are adjacent to current.
	random_shuffle(adjs)
	for v in adjs:
		if v is not in p:
			dfs(v)

Let start = random(0, n-1)   # a random number between 0 and n-1, inclusive
dfs(start)
output(p)

Clearly, the output of this algorithm is always a permutation of the numbers from 0 to n-1. However, as the algorithm uses randomness, there may be multiple possible outputs. Please compute and return the number of different permutations the algorithm may return.

Definition

Class:: DFSCount
Method:: count
Parameters:: String[]
Returns:: long
Method signature:: long count(String[] G)
(be sure your method is public)

Constraints

n will be between 1 and 14, inclusive.
G will contain exactly n elements.
Each element in G will contain exactly n characters.
Each character in G will be 'N' or 'Y'.
For any valid i, G[i][i] = 'N'.
For any valid i and j, G[i][j] = G[j][i].
The graph described by G will be connected.

Examples

```
{"NYY",
 "YNY",
 "YYN"}
```
```
Returns: 6
```
G describes a complete graph with 3 vertices. There are 3! = 6 permutations of vertices, and we can easily verify that each of these permutations can appear as the output of Ciel's algorithm.
```
{"NYNN",
 "YNYN",
 "NYNY",
 "NNYN"}
```
```
Returns: 6
```
This time the graph is a line: 0 - 1 - 2 - 3. These are the possible outputs: 0,1,2,3 1,0,2,3 1,2,3,0 2,1,0,3 2,3,1,0 3,2,1,0
```
{"NYYY",
 "YNYY",
 "YYNN",
 "YYNN"}
```
```
Returns: 16
```
This graph looks as follows: 2 / \ 0---1 \ / 3 There are 16 possible permutations: 0,1,2,3 0,1,3,2 0,2,1,3 0,3,1,2 1,0,2,3 1,0,3,2 1,2,0,3 1,3,0,2 2,0,1,3 2,0,3,1 2,1,0,3 2,1,3,0 3,0,1,2 3,0,2,1 3,1,0,2 3,1,2,0

{"NYYYYYYYYYYYYY",
 "YNYYYYYYYYYYYY",
 "YYNYYYYYYYYYYY",
 "YYYNYYYYYYYYYY",
 "YYYYNYYYYYYYYY",
 "YYYYYNYYYYYYYY",
 "YYYYYYNYYYYYYY",
 "YYYYYYYNYYYYYY",
 "YYYYYYYYNYYYYY",
 "YYYYYYYYYNYYYY",
 "YYYYYYYYYYNYYY",
 "YYYYYYYYYYYNYY",
 "YYYYYYYYYYYYNY",
 "YYYYYYYYYYYYYN"}

Returns: 87178291200

The answer is 14!

```
{"N"}
```
```
Returns: 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.