Considering a \(N\)-vertex directed a graph that has for each \(i \, (1 \leq i \leq M)\) an edge from Vertex \(A_i\) to Vertex \(B_i\), the answer is the lexicographically smallest sequence of topologically sorted vertices.

One of the common approaches for problems concerning the lexicographical order is to determine the elements in the order of appearances. For example, the following algorithm is possible to find the topologically sorted result in order.

• Prepare an empty array \(S\).
• While there exists a vertex with indegree \(0\), repeat the following procedures.
  • Choose a vertex with degree \(0\), denoting by \(u\).
  • Push \(u\) to the tail of \(S\).
  • Remove \(u\) and edges going out from \(u\).
• When the algorithm has ended, if one or more vertices remain in the graph, then it is impossible to sort topologically. If no vertices remain, \(S\) is the result of topologically sorted vertex.

If we always choose the vertex with smallest index and indegree \(0\), we obtain the lexicographically smallest \(S\).

Sample code