RelabelingOfGraph
SRM 365 · 2007-09-12 · by Xixas
SRM 365 · 2007-09-12 · by Xixas · Graph Theory
Problem Statement
Problem Statement
Given a directed graph on n vertices, your task is to label its vertices as follows:
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.
- 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.
Return the labeling as aint[] , where the i-th element of theint[] 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 emptyint[] .
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 }
4)
{"0000", "0010", "1000", "0000"}
Returns: {2, 0, 1, 3 }
Submissions are judged against all 152 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RelabelingOfGraph with a public method vector<int> renumberVertices(vector<string> m) · 152 test cases · 2 s / 256 MB per case