TopCoder problem "SplitSubgraphs" used in TCCC06 Round 2B (Division I Level Three)



Problem Statement

    A graph is called split if the vertices can be partioned into two non-empty sets A and B such that no two distinct vertices in A are adjacent, and all pairs of distinct vertices in B are adjacent. Considering all possible ways of removing 0 or more nodes from the given graph, return how many of the resulting subgraphs are split. Two subgraphs are considered distinct if the sets of removed nodes are distinct. Character i in element j of graph is '1' if nodes i and j are adjacent, and '0' if not.
 

Definition

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

Constraints

-graph will contain between 1 and 20 elements, inclusive.
-Each character in graph will be '0' or '1'.
-Each element of graph will contain exactly N characters, where N is the number of elements in graph.
-Character i of element i of graph will always be '0'.
-Character i of element j of graph will equal character j of element i.
 

Examples

0)
    
{"011",
 "101",
 "110"
}
Returns: 4
Every subgraph with at least 2 vertices is split.
1)
    
{"0"}
Returns: 0
Note that A and B must both be non-empty.
2)
    
{"0000",
 "0000",
 "0001",
 "0010"
}
Returns: 11
3)
    
{"0100",
 "1000",
 "0001",
 "0010"
}
Returns: 10
4)
    
{"01100",
 "10110",
 "11001",
 "01001",
 "00110"}
Returns: 24

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10112&pm=4648

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Yarin , Olexiy

Problem categories:

Graph Theory, Recursion