ConnectedSubgraph

This problem is about simple undirected graphs. (That is, each edge is bidirectional, there are no self-loops, and each pair of vertices is connected by at most one edge.)

Suppose that we are given a graph G and a set S that is a non-empty subset of the vertices of G. Let G(S) be a new graph. The vertices of G(S) are the vertices in the set S. Two vertices in G(S) are connected by an edge if and only if they are connected in the original graph G. Each such graph G(S) is called an induced subgraph of the graph G.

A graph with n vertices has 2^n - 1 distinct induced subgraphs. (Note that the set S must be non-empty. One of the 2^n - 1 induced subgraphs is the graph G itself.)

You are given an ints k. Construct a simple undirected graph G with the following properties:

• The vertices in G are numbered 0 through n-1, where n is their number.
• The value of n must be between 1 and 20, inclusive.
• Among the induced subgraphs of G there are exactly k connected graphs.

For each k that satisfies the given constraints there is at least one such graph G. If there are multiple solutions, you may choose any of them. Return the description of your chosen graph G: a String[] res with n elements, each containing n characters. For each i and j, res[i][j] should be 'Y' if there is an edge connecting vertices i and j, otherwise res[i][j] should be 'N'. Note that for each i, res[i][i] should be 'N'.