Algorithms-1 04

Topological sorting problem

When talking about DFS, there are two correctness-related theorems (see lecture 3)

Parenthesis theorem theorem

White path theorem theorem

---

Input

Output

Solution

Run and return vertices in the descending order by their “finished” time

---

Strongly connected component (SCC) definition

Input

Output

Solution

Run , calculate , run in the descending order by and return each resulting -tree as a SCC

---

Partition of a bipartite graph

Input

Output

Solution

Let , run , each vertex with even distance from is in , each vertex with odd distance from is in

---

Distances in a graph

Input

Output

Solution

Run topological sorting and then recursively (DP) calculate distances of vertices after in the topological ordering