Skip to content

Course Schedule

  • Title: Course Schedule
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1679
  • Secondary topics: Kahn topological sort, Indegree counting, Directed cycle detection
  • Difficulty: medium
  • Subtype: Find a topological order or prove a directed cycle exists
  • Status: solved
  • Solution file: courseschedule.cpp

Why Practice This

This is the cleanest topological-sort problem on CSES. It teaches the exact reason Kahn's algorithm works:

  • indegree 0 means "no remaining prerequisites"
  • removing such a node preserves the same structure on the smaller graph
  • if the process gets stuck early, a cycle must exist

Recognition Cue

Reach for topological sort when:

  • the graph is directed
  • edges mean prerequisites or dependencies
  • you need one valid order that respects all dependencies
  • a cycle should make the task impossible

The cleanest wording smell is:

  • "take course/task b only after course/task a"

That is usually a DAG-ordering question.

Problem-Specific Transformation

The course story hides a simple directed graph:

  • a -> b means a must come before b

Then the task becomes:

  • either produce one topological order of this directed graph
  • or prove no such order exists because a directed cycle remains

That is exactly the statement Kahn's indegree process was built for.

Core Idea

For each course, store its current indegree.

Then:

  1. Push every node with indegree 0 into a queue.
  2. Repeatedly pop one node, append it to the answer, and "remove" all outgoing edges by decrementing neighbor indegrees.
  3. Whenever a neighbor's indegree becomes 0, push it into the queue.

This is Kahn's algorithm.

Why does it detect cycles?

  • In a DAG, there is always at least one node with indegree 0, so the process can keep going until all nodes are removed.
  • If some nodes remain but none has indegree 0, then every remaining node still depends on another remaining node, which means a directed cycle exists.

So the final check is:

if answer size < n, print IMPOSSIBLE

Otherwise the produced order is a valid topological ordering.

Complexity

  • build indegrees and adjacency lists: O(n + m)
  • Kahn traversal: O(n + m)
  • total: O(n + m)

Pitfalls / Judge Notes

  • The graph is directed. Add only a -> b, not both directions.
  • Decrement indegree exactly once per outgoing edge.
  • Multiple valid topological orders can exist; any one is accepted.
  • A failed topological sort is a cycle signal, not just "bad luck with queue order".

Reusable Pattern

Solutions