10. Graphs

Topological sort

0 of 5 activities0%

Reading 1

Dependencies first

Open

Topological order: for every directed edge u→v, u appears before v.

Only exists for DAGs (directed acyclic graphs). Kahn’s algorithm: queue sources with indegree 0. DFS postorder reverse also works.

Use for build systems, course prerequisites.

// Kahn: reduce indegrees, queue zeros

Check 2

Open

Topological sort requires

Fill in 3

Open

Try it 4

Open

Count indegree.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n m. If m>=n print cycle (pigeon on undirected connected idea simplified: if m>=n print cycle else ok). For teaching only.

main.cpp

Loading editor…