Community | Topcoder Archive

Problem Statement

Given an undirected graph, G, you want to find a subgraph G' of G such that the ratio (number of edges in G')/(number of nodes in G') is maximized. An edge is in G' if both of its endpoints are in G'. Return the maximum ratio.

The graph will be given as a String[] where character j of element i is '1' if and only if i and j are connected.

Definition

Class:: Community
Method:: find
Parameters:: String[]
Returns:: double
Method signature:: double find(String[] g)
(be sure your method is public)

Notes

G' must have at least one node in it for the ratio to be defined.

Constraints

g will contain between 2 and 50 elements, inclusive.
g will be square and each character will be '0' or '1'.
g will be symmetric and have no self-edges.

Examples

```
{"0111",
 "1010",
 "1100",
 "1000"}
```
```
Returns: 1.0
```
Selecting the 3 nodes that form a triangle gives us a ratio of 1.
```
{"0111",
 "1011",
 "1101",
 "1110"}
```
```
Returns: 1.5
```
This is a complete graph on 4 vertices, which has 6 edges. Selecting G'=G gives us 6/4.

{"0010000010",
 "0010000000",
 "1101000000",
 "0010100000",
 "0001001000",
 "0000000011",
 "0000100000",
 "0000000000",
 "1000010000",
 "0000010000"}

Returns: 0.8

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.