ChromaticNumber | Topcoder Archive

Problem Statement

Fox Ciel has an undirected simple graph with N vertices. This graph has a special property: the degree of each vertex is at least N-3.

Ciel wants to color the vertices of this graph. If there is an edge between vertex u and vertex v, she must use different colors for u and v.

You are given a String[] graph. The vertices of the graph are labeled 0, 1, 2, and so on. If the j-th character of the i-th element of graph is 'Y', there is an edge between vertex i and vertex j. If the j-th character of the i-th element of graph is 'N', there is no edge between vertex i and vertex j. Return the minimal number of colors required to color this graph.

Definition

Class:: ChromaticNumber
Method:: minColors
Parameters:: String[]
Returns:: int
Method signature:: int minColors(String[] graph)
(be sure your method is public)

Notes

A graph is called simple if there are no self-loops and each pair of vertices is connected by at most one direct edge.
The degree of vertex v is the number of vertices that are adjacent to v.
The constraint "the degree of each vertex is at least N-3" is also satisfied for any simple graph with N=1 or N=2.

Constraints

graph will contain between 1 and 50 elements, inclusive.
Each element of graph will contain exactly N characters, where N is the number of elements in graph.
Each character in each element of graph will be either 'Y' or 'N'.
For all i, the i-th character of the i-th element of graph will be 'N'.
For all i and j, the i-th character of the j-th element of graph will be equal to the j-th character of the i-th element of graph.
Each element of graph will contain at least N-3 'Y', where N is the number of elements in graph.

Examples

```
{"N"}
```
```
Returns: 1
```
This graph contains only one vertex, so Ciel can color this graph with one color.
```
{"NYY",
 "YNN",
 "YNN"}
```
```
Returns: 2
```
Ciel can color this graph with two colors as follows.

{"NYNN",
 "YNNN",
 "NNNY",
 "NNYN"}

Returns: 2

{"NYNY",
 "YNYY",
 "NYNN",
 "YYNN"}

Returns: 3

{"NYYYYYYY",
 "YNYYYYYY",
 "YYNYYYYY",
 "YYYNYYYY",
 "YYYYNYYY",
 "YYYYYNYY",
 "YYYYYYNY",
 "YYYYYYYN"}

Returns: 8

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.