I was working on this problem: http://codeforces.com/contest/510/problem/C
I spent a fair bit of time on it, and I knew while solving it that it was a topological sorting problem. However, I have gone through the USACO training pages to learn my algorithms, which doesn't have a section on topological sorting. I know standard graph algorithms like bfs,dfs,warshall,dijkstra, etc. but I don't know how to solve these topological sorting problems. The editorial mentions that this is a classic topological sort problem.
My question is, how can dfs be applied to solve this problem, and where can I find more theory/practice problems to practice topological sorting.
Thanks!
Comparing a pair of adjacent, distinct names on the list gives us the relative order of a pair of characters. If "tourist" directly preceded "toosimple," for example, we could determine that 'u' precedes 'o'. Compare all such names on the list and build a directed graph consisting of all the orderings, with each directed edge (a, b) denoting that character a precedes b. The graph should contain at most n — 1 edges (less if the list contains adjacent, lexicographically equal names) and at most 26 vertices (1 vertex for each letter in the alphabet). The final alphabet is simply the topologically sorted graph, with unused characters inserted anywhere in any order.
Check out this link for an explanation of what topological sorting is: http://www.geeksforgeeks.org/topological-sorting/
You might try these two problems on Spoj
http://www.spoj.com/problems/RPLA/ http://www.spoj.com/problems/TOPOSORT/
There are a couple of algorithms for Toposort. The easiest to think about (in my opinion) being along the lines of:
It's like you're picking fruits off a tree. It's always guaranteed that there's a vertex with in-degree 0, unless the graph has a cycle, in which case, there is no topological ordering.
Befor do topsort on a graph,graph have to be DAG.Could you please help me how i check whether it is DAG or not? Thanks in Advance
You would apply the topological sort algorithm I mentioned using a queue to keep all the in-degree 0 vertices. At the end of the algorithm, if your vector has a size less than the number of vertices, then there was a cycle somewhere! This happens when your queue is empty but not all vertices in the graph have been pushed to it at some time.
This way, there's no need to check that it's a DAG beforehand!
When there are still nodes remaining, but none of them as IN-degree as ZERO, you can be sure that a cycle exists in the graph.
Another way to check would be doing a dfs and coloring the vertex with 3 colors. 1. WHITE — Unprocessed 2. GREY — In Process 3. BLACK — Processed
If you encounter GREY node while doing DFS traversal ==> CYCLE.