Topological Sort Question

Revision en1, by send_nodes, 2015-08-13 04:23:53

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!

Tags graph, topological sort

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English send_nodes 2015-08-13 04:23:53 707 Initial revision (published)