srm704 middium ConnectedComponentConstruction
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 a s. Construct a simple undirected graph with the following properties: 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]. If there is no such graph, return an empty . Otherwise, return a 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.
note
I used union find tree. In this problem, there is not hard constraint. so I can user uft for checking the number of the verticies.
