Editorial for Resources


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: doncho

The task is a classical Topological sort

It can be solved by repeating three steps:

  1. Find the best vertex

    • With no incoming edges
    • With smallest lexicographical order

      func getBest():
        vertices = []
      
        # counts is a helper object, counting the incoming edges for v at counts[v]
        for each (vertex, count) of this._counts):
            if count > 0 or vertex is used:
                continue
            add vertex to vertices
      
        return best vertex of vertices
      
  2. Add it to result

  3. Remove all outgoing edges from it

    • To remove an edge, just mark the vertex as used:
    • Decrease the count of each neighbor of vertex

      func removeEdgesOf(vertex):
         used.add(vertex);
         for each neighbor of vertex: 
             counts[vertex] -= 1
      

Comments

There are no comments at the moment.