StarsInGraphs | Topcoder Archive

Problem Statement

You are given the adjacency matrix of a directed graph as a String[] adjacencyMatrix. The j-th character of the i-th element of adjacencyMatrix will be '1' if there is an edge going from the i-th vertex to the j-th, or '0' otherwise. A star in a directed graph is defined as follows: it is comprised of a central vertex and at least three distinct edges emanating from it, which we will call the rays of the star. The number of rays in a star is not bounded; the only restriction is that there must be at least 3 of them. The number of distinct stars for which a vertex V is central will be called the star number of V. For example, if V has 5 edges emanating from it then its star number is 16 = 10 + 5 + 1 since it is central for 10 stars with 3 rays, 5 stars with 4 rays, and 1 star with 5 rays. We will call a path in our graph starry if it satisfies two conditions:

Each vertex belonging to the path has a non-zero star number not exceeding C.
Given two subsequent vertices V_i and V_i+1 in the path the star number of V_i+1 is not less than the star number of V_i.

Given the directed graph in the form of its adjacency matrix return the number of vertices in the longest starry path it contains. If there is a starry path of infinite length in the graph return -1. If there are no starry paths (all vertices have star numbers either 0 or greater than C) return 0.

Definition

Class:: StarsInGraphs
Method:: starryPaths
Parameters:: String[], int
Returns:: int
Method signature:: int starryPaths(String[] adjacencyMatrix, int C)
(be sure your method is public)

Notes

Two stars are considered distinct if either their central vertices are distinct or the sets of rays are distinct.

Constraints

adjacencyMatrix will contain between 2 and 50 elements, inclusive.
The number of characters in each string of the adjacencyMatrix will be equal to the total number of elements in adjacencyMatrix.
Every character of each element of adjacencyMatrix will be either '0' (zero) or '1' (one).
The i-th character of the i-th element of adjacencyMatrix will be '0'.
C will be between 1 and 109, inclusive.

Examples

```
{"01110",
 "10111",
 "00000",
 "00000",
 "00000"}
```
```
1000
```
```
Returns: 2
```
The starry path 0 -> 1 is the longest one. Vertex 0 has star number 1, vertex 1 has star number 5, and all other vertices have star numbers 0.
```
{"01011",
 "00111",
 "10011",
 "00000",
 "00000"}
```
```
1
```
```
Returns: -1
```
Vertices 0, 1, and 2 have star numbers 1 and form a cycle, thus we have an infinite starry path.
```
{"0111",
 "0000",
 "0000",
 "0000"}
```
```
1
```
```
Returns: 1
```
This time the longest starry path consists of a single vertex.
```
{"01111",
 "00000",
 "00000",
 "00000",
 "00000"}
```
```
4
```
```
Returns: 0
```
Vertex 0 has star number 5 and the rest of the vertices have a zero star number, and thus none of them can appear in a starry path.

{"010001100",
 "001001100",
 "000101110",
 "000010111",
 "000001111",
 "010000000",
 "000110000",
 "000100001",
 "100001000"}

Returns: 5

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.