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

0)

 ```{"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}.
1)

 ```{"011", "101", "110"}```
`Returns: 1`
 All nodes are connected so there is just one big clique.
2)

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

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4687

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7992&pm=4687

lars2520

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Graph Theory