Connection Status:
Competition Arena > DFSCount

DFSCount

SRM 713 · 2017-02-20 · by cgy4ever

SRM 713 · 2017-02-20 · by cgy4ever · Dynamic Programming, Graph Theory
Class Name: DFSCount
Return Type: long
Method Name: count
Arg Types: (vector<string>)
Problem Statement

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.

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

1)
{"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

2)
{"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

3)
{"NYYYYYYYYYYYYY",
 "YNYYYYYYYYYYYY",
 "YYNYYYYYYYYYYY",
 "YYYNYYYYYYYYYY",
 "YYYYNYYYYYYYYY",
 "YYYYYNYYYYYYYY",
 "YYYYYYNYYYYYYY",
 "YYYYYYYNYYYYYY",
 "YYYYYYYYNYYYYY",
 "YYYYYYYYYNYYYY",
 "YYYYYYYYYYNYYY",
 "YYYYYYYYYYYNYY",
 "YYYYYYYYYYYYNY",
 "YYYYYYYYYYYYYN"}
Returns: 87178291200

The answer is 14!

4)
{"N"}
Returns: 1

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

Coding Area

Language: C++17 · define a public class DFSCount with a public method long long count(vector<string> G) · 129 test cases · 2 s / 256 MB per case

Submitting as anonymous