BridgesAndCutVertices
TCO20 South Asia Parallel · 2020-08-15 · by misof
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
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
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.
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
6
9
Returns: {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 6, 9, 7, 9, 7, 8, 7, 10, 8, 10, 0, 11, 0, 12, 11, 12, 8, 13, 8, 14, 13, 14 }
14
17
Returns: {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 14, 17, 15, 17, 15, 16, 15, 18, 16, 18, 0, 19, 0, 20, 19, 20, 16, 21, 16, 22, 21, 22 }
12
1
Returns: {0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 0, 11, 0, 12, 0, 13, 0, 14, 13, 14, 0, 15, 0, 16, 15, 16 }
Submissions are judged against all 182 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BridgesAndCutVertices with a public method vector<int> construct(int B, int C) · 182 test cases · 2 s / 256 MB per case