TopCoder problem "FractalWheels" used in TCO09 Championship (Division I Level One)



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)
    
3
{
"0 1,1 2"
}
Returns: { }
A fractal wheel must have at least 4 vertices.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10430

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13765&pm=10430

Writer:

eleusive

Testers:

PabloGilberto , Yarin , ivan_metelsky

Problem categories:

Graph Theory, Recursion