RelabelingOfGraph | Topcoder Archive

Problem Statement

Given a directed graph on n vertices, your task is to label its vertices as follows:

Each vertex must be labeled with a distinct number between 0 and n-1, inclusive.
For every edge in the graph from vertex v1 to vertex v2, v2's label must be greater than v1's label.

You are given a String[] m containing the adjacency matrix of the original graph. The j-th character of the i-th element of m is '1' (one) if there is an edge in the graph from the i-th vertex to the j-th vertex, or '0' (zero) otherwise.

Return the labeling as a int[], where the i-th element of the int[] is the label of the i-th vertex. If there is more than one possible labeling, return the one that comes first lexicographically. If there is no valid way to label the vertices, return an empty int[].

Definition

Class:: RelabelingOfGraph
Method:: renumberVertices
Parameters:: String[]
Returns:: int[]
Method signature:: int[] renumberVertices(String[] m)
(be sure your method is public)

Notes

int[] a comes before int[] b lexicographically if a[i] &lt b[i] , where i is the first position in which a and b differ.

Constraints

m will contain between 1 and 50 elements, inclusive.
Each element of m will contain exactly n characters, where n is the number of elements in m.
Each character in each element of m will be '1' (one) or '0' (zero).
The i-th character of the i-th element of m will be '0'.

Examples

{"0100", "0010", "0001", "0000"}

Returns: {0, 1, 2, 3 }

A chain consisting of 4 vertices.

```
{"010", "001", "100"}
```
```
Returns: { }
```
We have a cycle of 3 vertices and hence can not enumerate the vertices in the desired fashion.

{"00001", "00010", "00000", "00001", "00100"}

Returns: {0, 1, 4, 2, 3 }

```
{"0"}
```
```
Returns: {0 }
```

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.