Problem Statement
This problem is about graphs. All graphs in this problem are simple undirected graphs. (I.e., no self-loops and no multiple edges.)
A bridge is an edge such that its removal increases the number of connected components.
A cut vertex (a.k.a. articulation point) is a vertex such that its removal (along with the removal of all edges incident with this vertex) increases the number of connected components.
For example, consider the graph on vertices {0, 1, 2, 3, 4, 5, 6, 7} with edges 0-1, 2-3, 3-4, 5-6, 6-7, and 5-7. Its current connected components are {0, 1}, {2, 3, 4}, and {5, 6, 7}. There are three bridges: the edges 0-1, 2-3, and 3-4. There is one cut vertex: the vertex 3.
You are given the ints B and C. Construct a graph with exactly B bridges and exactly C cut vertices.
The set of vertices of your graph is the set {0, 1, ..., 49}. The graph must have at most 200 edges. If the edges are x0-y0, x1-y1, ..., return the int[] {x0, y0, x1, y1, ...}.
Definition
- Class:
- BridgesAndCutVertices
- Method:
- construct
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] construct(int B, int C)
- (be sure your method is public)
Notes
- For the given constraints a solution always exists, and any valid solution will be accepted.
Constraints
- B will be between 0 and 23, inclusive.
- C will be between 0 and 23, inclusive.
Examples
4
1
Returns: {0, 1, 0, 2, 0, 3, 0, 4 }We need four bridges and one cut vertex. The return value corresponds to a graph with four edges: 0-1, 0-2, 0-3, and 0-4. All four edges are bridges and vertex 0 is the cut vertex. If we remove vertex 0 (and all edges from it), the connected component {0, 1, 2, 3, 4} will break into four new connected components, each consisting of a single vertex: {1}, {2}, {3}, and {4}.0
1
Returns: {0, 1, 0, 2, 1, 2, 2, 5, 5, 4, 4, 3, 3, 2, 2, 4, 6, 7, 6, 49, 7, 49 }In the graph described by the example return value the only cut vertex is vertex 2. 0 - 1 6 - 49 | / | / 2 - 5 7 | \ | 3 - 4