FractalWheels
TCO09 Championship · 2009-02-24 · by eleusive
TCO09 Championship · 2009-02-24 · by eleusive · Graph Theory, Recursion
Problem Statement
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 aString 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 emptyint[] . Otherwise, return a int[] with two elements: the depth and span of the fractal wheel, respectively.
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
If G is not a fractal wheel, then return an empty
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)
3
{
"0 1,1 2"
}
Returns: { }
A fractal wheel must have at least 4 vertices.
Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FractalWheels with a public method vector<int> describeWheel(int N, vector<string> edges) · 108 test cases · 2 s / 256 MB per case