Блог пользователя iamdumb

lexiographically smallest TOPOSORT

Автор iamdumb, история, 9 лет назад, По-английски

I was doing this question from spoj.And as far as I have understood it,it requires to find lexiographically smallest toposorting of a DAG.I have studied toposorting from here but implementing it leads me to different toposorting.Can anybody explain me is there any way to find lexiographical toposort ?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

i think this can work... one way to find a topsort is first remove a vertex with 0 indegree and proceed like that until i can't remove any vertex... we are going to proceed in this way but the candidates nodes to remove are going to be in a heap (or set) of pairs... the pair are going to contains (current indeg of the node, node itself). at the beginning put in the set all vertex with indegree 0, when we remove a vertex, update the indeg of all vertex neighbors to him, and proceed removing vertex until all are processed.

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

You can check your implementation/idea with this problem btw: https://jutge.org/problems/P14952_en

Also, my solution was the same that jcg described above.

→ Ответить