TopCoder problem "CliqueCount" used in SRM 256 (Division I Level Two)



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

Writer:

lars2520

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Graph Theory