Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

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.


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.