TreesCount | Topcoder Archive

Problem Statement

Little Dazdraperma likes graphs a lot. Recently she invented a new game for one person with graphs. She is given a connected undirected graph with N vertices numbered 0 to N-1, inclusive (see the notes for definitions of all unclear terms from graph theory). Each edge of the graph is labeled with a positive integer length. She tries to remove some edges (possibly 0) so that the resulting graph satisfies the following conditions:

The graph that remains is a tree with exactly N-1 edges.
For each v, 0 < v < N, the shortest distance between vertex 0 and vertex v is the same in the resulting graph and in the initial graph.

Dazdraperma wonders how many different resulting graphs that satisfy these conditions she can obtain. Two graphs are considered different if there are two different vertices such that one of the graphs contains an edge between these two vertices and another graph doesn't contain an edge between them.

You are given the representation of the initial graph as a String[] graph. This String[] contains exactly N elements and each element contains exactly N characters. The j-th character in the i-th element will be '0' if there is no edge between vertices i and j. Otherwise, it will be a character between '1' and '9' representing the length of the edge between vertices i and j.

Return the number of possible resulting graphs modulo 1000000007.

Definition

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

Notes

For the purpose of this problem, an undirected graph can be treated as a set of vertices and a set of edges, where each edge establishes a bidirectional connection between two different vertices.
A path between two different vertices A and B in a graph G is a sequence of 2 or more vertices v[0] = A, v[1], ..., v[L-1] = B, such that there's an edge in G between each two adjacent vertices in this sequence. A path is said to consist of edges between v[i] and v[i+1], where 0 ≤ i < L-1. The length of a path is the sum of lengths of all edges it consists of.
The path between vertices A and B in a graph G that has the minimum possible length is called the shortest path between them. The length of this path is called the shortest distance between A and B.
A graph G is connected if there's a path between each two different vertices of G.
A graph G is a tree if it is connected and contains exactly V-1 edges, where V is the total number of vertices in G.

Constraints

graph will contain between 2 and 50 elements, inclusive.
Each element of graph will contain the same number of characters as the number of elements in graph.
Each character in each element of graph will be between '0' and '9', inclusive.
For each i, the i-th character of i-th element of graph will always be '0'.
For each i and j, the i-th character of j-th element of graph will always be equal to the j-th character of i-th element of graph.
graph will represent a connected graph.

Examples

```
{"01",
 "10"}
```
```
Returns: 1
```
The graph is already a tree, so the answer is 1.
```
{"011",
 "101",
 "110"}
```
```
Returns: 1
```
The only possibility is to delete the edge between vertices 1 and 2.
```
{"021",
 "201",
 "110"}
```
```
Returns: 2
```
You can either delete the edge between vertices 1 and 2 or the edge between vertices 0 and 1.

{"0123",
 "1012",
 "2101",
 "3210"}

Returns: 6

More possibilities.

{"073542",
 "705141",
 "350721",
 "517031",
 "442304",
 "211140"}

Returns: 2

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.