DFSCountEasy | 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 can get from any vertex to any other vertex by following some sequence of edges.
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:: DFSCountEasy
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 13, 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
```
We have a complete graph with 3 nodes. So we have all 3! = 6 possible dfs sequence.
```
{"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

{"NYYYYYYYYYYYY",
 "YNYYYYYYYYYYY",
 "YYNYYYYYYYYYY",
 "YYYNYYYYYYYYY",
 "YYYYNYYYYYYYY",
 "YYYYYNYYYYYYY",
 "YYYYYYNYYYYYY",
 "YYYYYYYNYYYYY",
 "YYYYYYYYNYYYY",
 "YYYYYYYYYNYYY",
 "YYYYYYYYYYNYY",
 "YYYYYYYYYYYNY",
 "YYYYYYYYYYYYN"}

Returns: 6227020800

The answer is 13!.

```
{"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.