Connection Status:
Competition Arena > StarsInGraphs

StarsInGraphs

SRM 350 · 2007-05-23 · by Xixas

SRM 350 · 2007-05-23 · by Xixas · Dynamic Programming, Graph Theory, Math, Search
Class Name: StarsInGraphs
Return Type: int
Method Name: starryPaths
Arg Types: (vector<string>, int)
Problem Statement

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 Vi and Vi+1 in the path the star number of Vi+1 is not less than the star number of Vi.
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.

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
0)
{"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.

1)
{"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.

2)
{"0111",
 "0000",
 "0000",
 "0000"}
1
Returns: 1

This time the longest starry path consists of a single vertex.

3)
{"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.

4)
{"010001100",
 "001001100",
 "000101110",
 "000010111",
 "000001111",
 "010000000",
 "000110000",
 "000100001",
 "100001000"}
10
Returns: 5

Submissions are judged against all 178 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StarsInGraphs with a public method int starryPaths(vector<string> adjacencyMatrix, int C) · 178 test cases · 2 s / 256 MB per case

Submitting as anonymous