Note 1: it’s not possible to do topological order for non DAG graph Note 2: there can be multiple topological order Backward implementation by DFS pseudo-code DFS(𝑠, 𝑐𝑙𝑜𝑐𝑘, 𝑆):1𝑠.state ← active2for all edge 𝑢→𝑣:3if 𝑣.state = new:4𝑐𝑙𝑜𝑐𝑘← DFS(𝑣,𝑐𝑙𝑜𝑐𝑘)5else:6if 𝑣.state = active:7fail// it should not has cycle because it should be DAG89𝑠.state ← finish1011𝑆[𝑐𝑙𝑜𝑐𝑘]←𝑣12𝑐𝑙𝑜𝑐𝑘←𝑐𝑙𝑜𝑐𝑘−113return 𝑐𝑙𝑜𝑐𝑘topologicalSort(𝑠, 𝑉):1for all vertex 𝑣∈𝑉:2𝑣.state ← new34𝑆←∅5𝑐𝑙𝑜𝑐𝑘←|𝑉|6for all vertex 𝑣∈𝑉:7if 𝑣.state = new:8𝑐𝑙𝑜𝑐𝑘← DFS(𝑣,𝑐𝑙𝑜𝑐𝑘,𝑆)910return 𝑆[1…|𝑉|] Runtime 𝑂(|𝑉|+|𝐸|)