iamscrew's blog

help in topological sort (C. Fox and Names)
By iamscrew, 9 years ago, In English

Topological Sorting Help !!!

I read in tutorial to use the topological sorting in this question Fox and Names . I know that we have to find if there exists a order of alphabets such that name1<name2, name2<name3, name3<name4,and so on... but i could not help out how it is implemented and what is the basic idea behind this topological sorting algorithm? Can someone please help . ? Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

How to implement topological sort ? I think that the easiest way is to

  1. add to Queue vertives, which have zero in-degree.

Loop

  1. Get vertex from queue ( let's say it is vertex v) and add to result list

  2. Decrement all in-degree of neighbours of v. If a neighbour will have in-degree equal 0, add to queue

If not possible to continue, check if list contains all vertices ( if yes == no cycle found ) , result list contains topological order

Sorry for my english

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

    ok thanks, i get your idea, what if graph is given like this 1-2-3-4-5 and no vertex is having zero-in-degree. ? or this algorithm works for directed graph (1->2->3->4->5) . ?

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

Well, here's the main idea:-

Initial Observation :

name1 < name2, if and only if, the letter that comes up right after their longest common prefix in name1, is lexicographically lesser than that occurring in name2. Thus you get conditions of the type : (char1 should come before char2) , for each consecutive pair of names.

Final Idea : Imagine the letters as nodes, and the condition (char1 should come before char2) as a directed edge from char1 to char2. Thus the answer to the main question reduces to finding the topological sort of the directed graph described above.

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

    For implementation, refer the wikipedia article or my solution :-http://codeforces.com/contest/512/submission/9724237

    There are two corner cases as well, which I encourage you to find on your own.

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

If a graph has edges 1->2 2->3 2->4 What would the topological sort result into ?

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

    1,2,3,4 and 1,2,4,3 are both correct. The definition of topological sort is a sequence of all nodes in a graph where each node appears before all of his children.

    → Reply