Problem Statement |
| | An undirected graph is said to be a wheel if there exists a "center" vertex which is adjacent to all other vertices in the graph, and the subgraph induced by taking all other vertices of the graph is precisely a cycle. Additionally, any wheel must have at least 3 vertices in the cycle surrounding the center vertex. The span of a wheel is the degree of the center vertex. For example, the graph below is a wheel with span 4 (the center vertex is colored black).
We define a fractal wheel with depth d and span h as follows: a fractal wheel with depth 0 and span h is simply a wheel with span h.
To obtain a fractal wheel with depth d > 0 and span h, we first take a fractal wheel with depth d-1 and span h. Let V be the set of all vertices at distance d from the center vertex of this fractal wheel. For each vertex u in V, add to the graph a new wheel with span h such that its center vertex is u. Each added wheel must be vertex-disjoint from the other added wheels. The resulting graph is a fractal wheel with depth d and span h, and the center vertex of the resulting fractal wheel is the same as the center vertex of the initial fractal wheel with depth d-1.
For example, the graph below is a fractal wheel with depth 1 and span 4 (note that adding or removing any edges from this graph would result in a graph which is not a fractal wheel):
Given a graph G with N vertices numbered 0 to N-1, inclusive, you must determine if G is a fractal wheel. Concatenate the elements of edges to get a String containing a comma-separated list of edges describing G. Each edge is formatted (quotes for clarity) "u v", which denotes that there is an edge between vertices u and v in G.
If G is not a fractal wheel, then return an empty int[]. Otherwise, return a int[] with two elements: the depth and span of the fractal wheel, respectively. |
| |
Definition |
| | | Class: | FractalWheels | | Method: | describeWheel | | Parameters: | int, String[] | | Returns: | int[] | | Method signature: | int[] describeWheel(int N, String[] edges) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The distance between two vertices in a graph is the length of the shortest path between them (or infinity if there is no path). |
| - | The degree of a vertex v in a graph G is the total number of vertices in G which are adjacent to v. |
| |
Constraints |
| - | N will be between 2 and 1000, inclusive. |
| - | edges will contain between 1 and 50 elements, inclusive. |
| - | Each element of edges will contain between 0 and 50 characters, inclusive. |
| - | The elements of edges, when concatenated together, will contain a comma-separated list of edges. Let's call the concatenated string E. |
| - | Each edge in E will be formatted "u v" (quotes for clarity), where u and v are integers between 0 and N-1, inclusive, with no extra leading zeroes, and u is strictly less than v. |
| - | All edges in E will be distinct. |
| - | E will contain at least one edge. |
| |
Examples |
| 0) | |
| | 5 | {
"","0 1,0 2,0 3,0 4,",
"1 2,2 3,3 4,1 4"
} |
| Returns: {0, 4 } | | The first graph from the problem statement. |
|
|
| 1) | |
| | 21 | {
"0 1,0 2,0 3,0 4,1 2,1 4,1 5,1 6,1 7,1 8,2 3,2 9,2 ",
"10,2 11,2 12,3 4,3 13,3 14,3 15,3 16,4 17,4 18,4 1","",
"9,4 20,5 6,5 8,6 7,7 8,9 10,9 12,10 11,11 12,13 14",
",13 16,14 15,15 16,17 18,17 20,18 19,19 20",""
} |
| Returns: {1, 4 } | | The second graph from the problem statement. |
|
|
| 2) | |
| | 13 | {
"0 1,0 2,0 3,1 2,1 3,1 4,1 5,1 6,2 3,2 7,2 8,2 9,3 ",
"10,3 11,3 12,4 5,4 6,5 6,7 8,7 9,8 9,10 11,10 12,1",
"1 12,0 7"
} |
| Returns: { } | | Here we have a fractal wheel with depth 1 and span 3, but with an extra edge from the center vertex to an outer-layer vertex. |
|
|
| 3) | |
| | 11 | {
"0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,1 2,1 10,",
"2 3,3 4,4 5,5 6,6 7,7 8,8 9,9 10"
} |
| Returns: { } | | A fractal wheel with depth 0 and span 10, but with a missing edge that should be incident to the center. |
|
|
| 4) | |
| | | Returns: { } | | A fractal wheel must have at least 4 vertices. |
|
|