send_nodes's blog

Topological Sort Question
By send_nodes, history, 9 years ago, In English

I was working on this problem: http://codeforces.net/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!

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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/

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You might try these two problems on Spoj

http://www.spoj.com/problems/RPLA/ http://www.spoj.com/problems/TOPOSORT/

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

There are a couple of algorithms for Toposort. The easiest to think about (in my opinion) being along the lines of:

  1. Pick any vertex with in-degree 0.
  2. Remove it from the graph and update in-degrees of outgoing vertices, then push it into some vector.
  3. Repeat 1 while there are still vertices in the graph.

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.

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

    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

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

      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!

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

      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.

      → Reply