### iamscrew's blog

By iamscrew, 9 years ago,

# 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.

• 0

 » 9 years ago, # | ← Rev. 2 →   0 How to implement topological sort ? I think that the easiest way is to add to Queue vertives, which have zero in-degree. Loop Get vertex from queue ( let's say it is vertex v) and add to result list 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 orderSorry for my english
•  » » 9 years ago, # ^ |   0 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) . ?
•  » » » 9 years ago, # ^ |   0 You can't do a topological sort in an undirected graph.
•  » » » » 9 years ago, # ^ |   0 ok thanks.
 » 9 years ago, # |   0 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.
•  » » 9 years ago, # ^ |   0 For implementation, refer the wikipedia article or my solution :-http://codeforces.com/contest/512/submission/9724237There are two corner cases as well, which I encourage you to find on your own.
 » 9 years ago, # |   0 If a graph has edges 1->2 2->3 2->4 What would the topological sort result into ?
•  » » 9 years ago, # ^ |   0 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.