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.
How to implement topological sort ? I think that the easiest way is to
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 order
Sorry for my english
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) . ?
You can't do a topological sort in an undirected graph.
ok thanks.
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.
For implementation, refer the wikipedia article or my solution :-http://mirror.codeforces.com/contest/512/submission/9724237
There are two corner cases as well, which I encourage you to find on your own.
If a graph has edges 1->2 2->3 2->4 What would the topological sort result into ?
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.