TopCoder problem "RelabelingOfGraph" used in SRM 365 (Division I Level Three)



Problem Statement

    Given a directed graph on n vertices, your task is to label its vertices as follows:
  1. Each vertex must be labeled with a distinct number between 0 and n-1, inclusive.
  2. 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] < 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
0)
    
{"0100", "0010", "0001", "0000"}
Returns: {0, 1, 2, 3 }
A chain consisting of 4 vertices.
1)
    
{"010", "001", "100"}
Returns: { }
We have a cycle of 3 vertices and hence can not enumerate the vertices in the desired fashion.
2)
    
{"00001", "00010", "00000", "00001", "00100"}
Returns: {0, 1, 4, 2, 3 }
3)
    
{"0"}
Returns: {0 }
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=7860


Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=10780&pm=7860


Writer:
 Xixas 

Testers:
 PabloGilberto


            , 
            Yarin


            , 
            Olexiy


            , 
            ivan_metelsky 

Problem categories:
 Graph Theory