SplitSubgraphs | Topcoder Archive

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

```
{"011",
 "101",
 "110"
}
```
```
Returns: 4
```
Every subgraph with at least 2 vertices is split.
```
{"0"}
```
```
Returns: 0
```
Note that A and B must both be non-empty.

{"0000",
 "0000",
 "0001",
 "0010"
}

Returns: 11

{"0100",
 "1000",
 "0001",
 "0010"
}

Returns: 10

{"01100",
 "10110",
 "11001",
 "01001",
 "00110"}

Returns: 24

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.