AcyclicBuilder | Topcoder Archive

Problem Statement

You are given a directed graph as a String[].The j-th character of the i-th element of graph is '1' (one) if there is a directed edge from the i-th vertex to the j-th vertex, and '0' (zero) if there is not. Return the minimal number of edges you need to delete to make it acyclic.

Definition

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

Notes

The graph may contain loops, i.e. edges from a vertex to itself. Each such edge forms a cycle. See example 1 for clarity.

Constraints

graph will contain between 1 and 21 elements, inclusive.
Each element of graph will contain exactly n characters, where n is the number of elements in graph.
Each element of graph will contain only the digits '0', '1'.

Examples

```
{"01", "10"}
```
```
Returns: 1
```
Delete any one edge.
```
{"10", "01"}
```
```
Returns: 2
```
This graph contains two loops, so you need to delete both to make it acyclic.
```
{"111", "111", "111"}
```
```
Returns: 6
```

{"1010", "1110", "0110", "1001"}

Returns: 5

{"010000000000000000000", "001000000000000000000", 
 "000100000000000000000", "000010000000000000000", 
 "000001000000000000000", "000000100000000000000", 
 "000000010000000000000", "000000001000000000000", 
 "000000000100000000000", "000000000010000000000", 
 "000000000001000000000", "000000000000100000000", 
 "000000000000010000000", "000000000000001000000", 
 "000000000000000100000", "000000000000000010000", 
 "000000000000000001000", "000000000000000000100", 
 "000000000000000000010", "000000000000000000001", 
 "100000000000000000000"}

Returns: 1

This graph is a cycle containing 21 vertices.

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.