GraphClique | Topcoder Archive

Problem Statement

You are given a String[] graphEdge representing an undirected graph.The j-th character of the i-th element of graphEdge is '1' (one) if there is an undirected edge between the i-th and j-th vertices, and '0' (zero) otherwise. Return a int[] containing the same number of elements as graphEdge, where the K-th (1-based) element is the number of different cliques of size K in the graph.

A clique is a non-empty set of vertices where every pair of vertices is directly connected by an edge in the graph. A clique of size K is a clique containing exactly K vertices.

Definition

Class:: GraphClique
Method:: allClique
Parameters:: String[]
Returns:: int[]
Method signature:: int[] allClique(String[] graphEdge)
(be sure your method is public)

Constraints

graphEdge will contain between 1 and 18 elements, inclusive.
Each element of graphEdge will contain exactly N characters, where N is the number of elements in graphEdge.
Each element of graphEdge will contain only the characters '0' (zero) and '1' (one).
The j-th character of the i-th element of graphEdge will be equal to the i-th character of the j-th element of graphEdge.
The i-th character of the i-th element of graphEdge will be '0' (zero).

Examples

```
{"0"}
```
```
Returns: {1 }
```
A single vertex is also a clique of size 1.
```
{"001","001","110"}
```
```
Returns: {3, 2, 0 }
```
Two cliques of size 2. One consists of vertices 0 and 2, and the other consists of vertices 1 and 2.

{"0110","1001","1001","0110"}

Returns: {4, 4, 0, 0 }

{"00110","00010","10000","11000","00000"}

Returns: {5, 3, 0, 0, 0 }

{"00011","00100","01011","10101","10110"}

Returns: {5, 6, 2, 0, 0 }

{"01111","10111","11011","11101","11110"}

Returns: {5, 10, 10, 5, 1 }

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.