AI Hints
Home›DSA in Python Tutorial›Groups and Cycles
DSA in Python · Lesson 86 of 132

Practice: Course Schedule

Can you finish every course?.

⏱ 2 min read▶ Video at 1:42:28🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A university says, to take course B, you must finish course A first. Given all the rules, can a student finish every course? Only if the rules don't go round in a circle. Pause. Which algorithm spots a cycle?

Practice: Course Schedule
From the video: Practice: Course Schedule
  • B needs A first
  • Can you finish them all?
  • Only without a cycle

Cycle detection with DFS

We colour each course. White means not visited yet. Grey means we're in the middle of exploring it. Black means it's finished, and safe. If depth first search ever reaches a grey course, we've gone round in a circle. Run it. The first plan works. The second has a loop, so it's impossible.

schedule.pypython
def can_finish(rules):
    state = {}
    def visit(c):
        if state.get(c) == "grey": return False
        if state.get(c) == "black": return True
        state[c] = "grey"
        if not all(visit(n) for n in rules.get(c, [])): return False
        state[c] = "black"
        return True
    return all(visit(c) for c in rules)

ok = {"maths": ["physics"], "physics": ["engineering"]}
bad = {"a": ["b"], "b": ["c"], "c": ["a"]}
print(can_finish(ok), can_finish(bad))
Output
True False

Three ways to find a cycle

You now know three ways to spot a cycle. Three colour depth first search, for directed graphs like this one. Kahn's algorithm, where the order comes out too short. And union find, for undirected graphs, where union returns false because two nodes were already connected.

keyvalue
DirectedDFS with colours
DirectedKahn's order too short
Undirectedunion find returns False
CostO(V + E)

Summary

A plan is possible only if its rules have no cycle. Three colour depth first search finds one, in O of V plus E. Next, a quiz on graphs.

Key takeaways
  • White, grey, black
  • Reach grey = cycle
  • No cycle = possible
Next up: Graphs Quiz — test yourself