[Leetcode] Topological Sort

Doc: https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit#heading=h.787pwa54vn0i


Implementation details:

1. Algorithm: DFS. (Kahn's algorithm needs to write codes find in-degrees of all vertices first. Therefore I don't recommend to implement Kahn's algorithm in a limited time. Besides, DFS could detect the cycle in the middle, not in the end.)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

(Copy from Wikipedia.)

2. Don't forget to reverse L for correct order.

3. If you don't want to reverse L, you might do topological sort on transpose graph instead.