Connection Status:
Competition Arena > DFSCountEasy

DFSCountEasy

SRM 713 · 2017-02-20 · by cgy4ever

SRM 713 · 2017-02-20 · by cgy4ever · Dynamic Programming, Graph Theory
Class Name: DFSCountEasy
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 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.

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
0)
{"NYY",
 "YNY",
 "YYN"}
Returns: 6

We have a complete graph with 3 nodes. So we have all 3! = 6 possible dfs sequence.

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)
{"NYYYYYYYYYYYY",
 "YNYYYYYYYYYYY",
 "YYNYYYYYYYYYY",
 "YYYNYYYYYYYYY",
 "YYYYNYYYYYYYY",
 "YYYYYNYYYYYYY",
 "YYYYYYNYYYYYY",
 "YYYYYYYNYYYYY",
 "YYYYYYYYNYYYY",
 "YYYYYYYYYNYYY",
 "YYYYYYYYYYNYY",
 "YYYYYYYYYYYNY",
 "YYYYYYYYYYYYN"}
Returns: 6227020800

The answer is 13!.

4)
{"N"}
Returns: 1

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

Coding Area

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

Submitting as anonymous