Topological sort by dfs Proposition In DAG, every edge(u, M) yields post/v)< post(ul 1/8Q929 o tree edge back edge forward edge!… 2/p e cross eage type edgell,v) tree u v I ju 4 OX back v u u forward cross V‖u 2/32021 Xiaojuan CaTopological sort by DFS Proposition In DAG, every edge (u,v) yields post[v] < post[u]. u v x y w z 1/ 2/ 3/ 4/5 6 7 8 9/ 10/ 11 12 • tree edge: • back edge: • forward edge: • cross edge: type edge(u,v) tree [u [v ]v ]u back [v [u ]u ]v forward [u [v ]v ]u cross [v ]v [u ]u 2/3/2021 Xiaojuan Cai 40