ConnectedComponentConstruction
SRM 704 · 2016-12-04 · by cgy4ever
SRM 704 · 2016-12-04 · by cgy4ever · Graph Theory
Problem Statement
Problem Statement
Any undirected graph can be decomposed into connected components.
Two vertices u and v belong to the same connected component if we can travel from u to v by following a sequence of zero or more consecutive edges.
The size of a connected component is the number of vertices it contains.
You are given aint[] s.
Construct a simple undirected graph with the following properties:
String[] .
Otherwise, return a String[] ret with n elements, each containing n characters.
For each i and j, ret[i][j] should be 'Y' if there is an edge between i and j in your graph.
Otherwise, ret[i][j] should be 'N'.
If there are multiple solutions, you may return any of them.
You are given a
- The number of vertices is n, where n is the number of elements in s.
- The vertices are numbered 0 through n-1.
- For each i, the size of the connected component that contains vertex i is exactly s[i].
Constraints
- s will contain between 1 and 50 elements, inclusive.
- Each element in s will be between 1 and |s|, inclusive.
Examples
0)
{2,1,1,2,1}
Returns: {"NNNYN", "NNNNN", "NNNNN", "YNNNN", "NNNNN" }
The answer is a graph that contains only one edge. This edge connects the vertices 0 and 3. This graph has four connected components: {0, 3}, {1}, {2}, and {4}.
1)
{1,1,1,1}
Returns: {"NNNN", "NNNN", "NNNN", "NNNN" }
Here the only correct answer is a graph with four vertices and no edges.
2)
{3,3,3}
Returns: {"NYY", "YNY", "YYN" }
This time one correct answer could be the complete graph on three vertices.
3)
{4,4,4,4,4}
Returns: { }
There is no solution.
4)
{1}
Returns: {"N" }
Submissions are judged against all 174 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ConnectedComponentConstruction with a public method vector<string> construct(vector<int> s) · 174 test cases · 2 s / 256 MB per case