Problem Statement
Time limit is 5 seconds.
Caterpillars are undirected trees in which there exists a path that contains every vertex of degree two or more.
An ASCII drawing of a sample caterpillar is shown below. Horizontal edges in the drawing show one possible path with the property mentioned above.
O O O O O O
\|/ | \ /
O --- O --- O --- O --- O --- O --- O
| |\ | |
O O O O O
You are given the String[] G containing the adjacency matrix of a small undirected graph with N labeled (i.e., distinct) vertices. Count all spanning trees of this graph that are caterpillars.
Definition
- Class:
- CaterpillarSpanningTrees
- Method:
- count
- Parameters:
- String[]
- Returns:
- long
- Method signature:
- long count(String[] G)
- (be sure your method is public)
Notes
- Note that we want the exact answer, not an answer modulo something. (The total number of spanning trees of a complete graph on 16 vertices fits into a 64-bit signed integer, so there can be no overflow.)
Constraints
- N will be between 1 and 16, inclusive.
- G will contain N elements.
- Each element of G will contain N characters.
- Each character in G will be 'Y' or 'N'.
- For each i, G[i][i] = 'N'.
- For each i and j, G[i][j] = G[j][i].
- The graph represented by G will be connected.
Examples
{"NYNN", "YNYY", "NYNY", "NYYN"}Returns: 3
The graph looks as follows: 0---1---2 \ / 3 It has three different spanning trees. Each of those is a caterpillar.{"N"}Returns: 1
The graph consists of a single isolated vertex. Its spanning tree also consists of that one vertex. By definition, this trivial tree is also a caterpillar so we do count it.{"NYYYYYY", "YNYYYYY", "YYNYYYY", "YYYNYYY", "YYYYNYY", "YYYYYNY", "YYYYYYN"}Returns: 15967
The complete graph on 7 vertices has 16807 different spanning trees. Almost all of them are caterpillars. The only unlabeled tree on seven vertices that is not a caterpillar is shown below. O---O---O---O---O | O | O There are 7 * 20 * 6 = 840 spanning trees of K_7 that look like this. Thus, there are 16807 - 840 distinct caterpillar spanning trees.{ "NYNNNNNNNNNNN", "YNYNNNNNNNNNN", "NYNYYNNNNNNNN", "NNYNNNNNNNNNN", "NNYNNYYYYYNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNNNN", "NNNNYNNNNNYYY", "NNNNNNNNNYNNN", "NNNNNNNNNYNNN", "NNNNNNNNNYNNN"}Returns: 1
This graph is the 13-vertex caterpillar shown below. 5 6 7 12 \|/ | 0 --- 1 --- 2 --- 4 --- 9 --- 11 | | | 3 8 10