iamdumb's blog

lexiographically smallest TOPOSORT

By iamdumb, history, 9 years ago, In English

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 ?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    can you show something :) It's difficult to imagine

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i have implemented and here it is: http://ideone.com/4TbCgM. actually there is no need to maintains in the set the current degree, if we have it in a array, when it is 0 then we add it to the set for processing later... if any doubts tell me..

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply