CliqueCount | Topcoder Archive

Problem Statement

An undirected graph is defined as a set of vertices with undirected edges connecting some of the pairs of vertices. A clique in an undirected graph is a non-empty subset of vertices where there is a direct connection between every pair of vertices in the subset. A maximal clique is a clique that is not a proper subset of any other clique. You will be given a graph as a String[] where the jth character of the ith element is a '1' if and only if vertices i and j are connected. Your method should return the number of maximal cliques in the graph.

Definition

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

Constraints

graph will contain between 1 and 20 elements, inclusive.
Each element of graph will contain as many characters as graph has elements.
Each character in graph will be '0' or '1'.
Character j of element i of graph will be the same as character i of element j for all i and j.
Character i of element i of graph will be '0' for all i.

Examples

```
{"010",
 "100",
 "000"}
```
```
Returns: 2
```
If the vertices are 0, 1, and 2, corresonding to the elements of the input, then the two maximal cliques are {0,1} and {2}.
```
{"011",
 "101",
 "110"}
```
```
Returns: 1
```
All nodes are connected so there is just one big clique.

{"00010000000000100000",
 "00110000000000000000",
 "01011001000000011000",
 "11101000000100010110",
 "00110000001100000000",
 "00000000010000000001",
 "00000000000000011001",
 "00100000000010000001",
 "00000000000100011000",
 "00000100000010000010",
 "00001000000000000010",
 "00011000100001000101",
 "00000001010000000000",
 "00000000000100000010",
 "10000000000000000010",
 "00110010100000000000",
 "00100010100000000000",
 "00010000000100000000",
 "00010000011001100000",
 "00000111000100000000"}

Returns: 28

```
{"00",
 "00"}
```
```
Returns: 2
```

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.