DSA sheet · Graphs · Topological sort pattern

Course Schedule

This is the first problem of the topological sort pattern, and the teacher calls it one of the most frequently asked graph questions in interviews. Courses depend on other courses, and we must say whether all of them can be finished. The graph idea underneath is: you can finish everything exactly when the "depends on" graph has no cycle. She solves it with BFS using indegrees (Kahn's algorithm), explains how the same idea looks with DFS and why BFS fits better, and leaves the DFS version as homework. I've written that homework too.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · BFS with indegrees (Kahn's algorithm), the teacher's solution
• Part B · The same indegree idea with DFS (her comparison)
• Part C · Homework: DFS cycle detection with a path marker
• Part D · Revision page

Part 0 · Before starting

Graph words we need

• Node (vertex): a thing. Here, a course.
• Edge: a connection between two nodes.
• Directed edge (a)→(b): it goes one way only. Here it means "a must be done before b". Undirected edges like (a)—(b) go both ways. They appear in other problems, but not here.
• Weighted edge: the edge carries a number (a cost). Course Schedule has no weights.
• Cycle: you can follow arrows and come back to where you started, e.g. (0)→(1)→(0).

Input forms, and building an adjacency list

Graphs come as an edge list (pairs like [1, 0]), an adjacency matrix (m[i][j] = 1 if there's an edge) or an adjacency list (for each node, the list of nodes its arrows point to). Here we get an edge list, and the teacher's first rule for any graph problem is: build the adjacency list first, because traversal keeps asking "where can I go from here?".

n = 3
edges = [[0, 1], [1, 2]]          # 0 goes to 1, 1 goes to 2
adj = [[] for _ in range(n)]
for a, b in edges:
    adj[a].append(b)              # directed: only one way
print(adj)                        # [[1], [2], []]

Her checklist for any graph problem: ① make the adjacency list, ② decide whether DFS or BFS fits better, ③ decide whether you need a visited array, or whether something else (the input itself, a counter, a special value) can play that role.

Visited, BFS and DFS in one line each

• Visited: a record of nodes already handled, so we don't process them twice or loop forever.
• BFS (Breadth First Search): use a queue (collections.deque). Pop from the front, push the neighbours at the back. The graph is explored in waves.
• DFS (Depth First Search): go deep along one path (with recursion, or an explicit stack), then come back.
• Connected components: separate pieces of a graph. Course graphs can be in pieces, e.g. courses 0→1 and courses 2→3 with nothing between them. Our solution must handle every piece.

Indegree

The indegree of a node is the number of arrows coming into it. For a course, that's how many prerequisites it is still waiting for. A course with indegree 0 waits for nothing, so it can be taken right now. The teacher calls it the "dependency count".

Topological sort

A topological order is a line-up of all nodes such that every arrow points forward: if a→b, then a comes before b. For courses, that's a valid study plan. It exists only if there is no cycle. In a cycle every course waits for another course in the same cycle, so none of them can go first.

from collections import deque
n = 4
adj = [[1, 2], [3], [3], []]      # 0 before 1 and 2, both before 3
indegree = [0] * n
for u in range(n):
    for v in adj[u]:
        indegree[v] += 1          # one more arrow coming into v
queue = deque(u for u in range(n) if indegree[u] == 0)
order = []
while queue:
    u = queue.popleft()           # u has nothing left to wait for
    order.append(u)
    for v in adj[u]:
        indegree[v] -= 1          # v waits for one thing less
        if indegree[v] == 0:
            queue.append(v)
print(order)                      # [0, 1, 2, 3]
print(len(order) == n)            # True, so there is no cycle

Part A · BFS with indegrees (Kahn's algorithm)

LeetCode 207 · Medium

1The question in simple words

There are numCourses courses, numbered 0 to numCourses − 1. You get a list prerequisites, where each pair [a, b] means "to take course a, you must first finish course b". Return True if it's possible to finish all courses, otherwise False.

Her real-life examples: you can't move to class 5 until you've passed the class 4 exam. You can't start DSA until you know some programming language. Those are dependencies.

• Example 1: n = 2, [[1, 0]]. 1 needs 0, and 0 needs nothing. Take 0, then 1. Two courses taken out of 2 → True.
• Example 2: n = 2, [[1, 0], [0, 1]]. 1 says "finish 0 first", and 0 says "finish 1 first". Each waits for the other forever: a cycle. We can't take even one course, 0 ≠ 2 → False.

  Example 1            Example 2 (cycle)
 (0) ──→ (1)          (0) ──→ (1)
                       ↑        │
                       └────────┘

Her bigger example (5 courses)

n = 5, prerequisites = [[1,0], [0,2], [2,3], [2,4], [3,4]]. In words: 1 needs 0, 0 needs 2, 2 needs 3, 2 needs 4, and 3 needs 4. Course 4 needs nothing.

 (4) ──→ (3)
  │       │
  ↓       │
 (2) ←────┘
  │
  ↓
 (0) ──→ (1)

2What the constraints tell us

• 1 ≤ numCourses ≤ 2000 → V (nodes) ≤ 2000. There's always at least one course.
• 0 ≤ prerequisites.length ≤ 5000 → E (edges) ≤ 5000. It can be 0: no edges at all means every course is free → True.
• prerequisites[i].length == 2 and 0 ≤ a, b < numCourses → plain integer node ids, so an indexed list works.
• All pairs are unique → no repeated edge. (The code works even if one repeats, because the indegree counts it twice and it's also decreased twice.)
• V + E ≤ 7000 → any O(V + E) method is instant. Even O(V·(V+E)), about 14 million steps, would pass. But the clean linear method is also the easiest one.

3Intuition: take whatever is free, then unlock the next ones

Picture a to-do board. Next to every course you write how many prerequisites it's still waiting for (its indegree).

• Any course showing 0 can be taken right now. Put it in a "ready" line (a queue).
• Take a course from the ready line. Now every course that was waiting for it gets one tick less on the board.
• When a course's count drops to 0, it joins the ready line.
• At the end, count how many courses you managed to take. If it's all of them → True. If some were never ready → there's a cycle → False.

4Building the logic from her example

Step 1: indegree = how many courses each one depends on

For each pair [course, pre], the course depends on one more thing, so indegree[course] += 1.

Only course 4 has indegree 0, so we can start with 4.

Step 2: the adjacency list (parent → children)

Once 4 is finished, where can we go next? To every course that was waiting for 4. The pairs don't tell us that directly. They're written from the child's side ("2 needs 4"). So we build the adjacency list the other way round:

• "1 needs 0" → finishing 0 helps 1 → 0 is the parent, 1 is its child → graph[0].append(1)
• "0 needs 2" → graph[2].append(0)
• "2 needs 3" → graph[3].append(2)
• "2 needs 4" → graph[4].append(2) (she skipped this one at first, noticed, and added it)
• "3 needs 4" → graph[4].append(3)

Step 3: BFS or DFS?

The teacher picks BFS. When a course is finished, all its children get their count lowered at the same moment, and any that reach 0 become ready together. A queue handles that naturally. (Part B shows the DFS version and why it's a bit clumsier for this.)

Step 4: run it

• Queue = [4] (the only indegree-0 course).
• Pop 4 (taken, count = 1). Its children are 2 and 3. Lower 2: 2 → 1. That's not 0, so 2 still waits for someone else (course 3). Lower 3: 1 → 0, so push 3.
• Pop 3 (count = 2). Child 2: 1 → 0. 2 was waiting for 3, and now it's free → push 2.
• Pop 2 (count = 3). Child 0: 1 → 0 → push 0.
• Pop 0 (count = 4). Child 1: 1 → 0 → push 1.
• Pop 1 (count = 5). It has no children. The queue is empty.

Count = 5 = numCourses → True. The order we took them in was 4, 3, 2, 0, 1.

Step 5: why "count == numCourses" is the whole test

Every course we pop is a course we really managed to take. So the answer is simply: did we pop all of them? We keep a count that goes up on every pop.

Step 6: do we need a visited array?

No. A course enters the queue only at the exact moment its indegree goes from 1 to 0, and that can happen only once (indegree never goes back up). So no course is pushed twice. The indegree reaching 0 is our "visited" signal. Courses that already start at 0 are pushed once at the start, and nothing lowers them again because no arrow points into them.

The cycle example, run through the same code

Example 2: [[1,0],[0,1]] → indegree = [1, 1]. No course has 0, so the queue starts empty, the loop never runs, and count = 0 ≠ 2 → False.

A cycle in the middle (the example she uses in the Course Schedule II video): n = 4, [[0,1],[1,2],[2,1],[1,3]]. 0 needs 1, 1 needs 2 and 3, 2 needs 1.

 (3) ──→ (1) ──→ (0)
          ↑ │
          │ ↓
          (2)        1 and 2 wait for each other

indegree = [1, 2, 1, 0]. Queue = [3]. Pop 3 (count 1) → lower 1: 2 → 1. Not 0. The queue is empty → count = 1 ≠ 4 → False. Course 0 isn't in the cycle, but it's stuck behind it.

5Approach steps

1. Make graph = n empty lists, and indegree = n zeros.
2. For each [course, pre]: graph[pre].append(course) and indegree[course] += 1.
3. Push every course with indegree 0 into a queue.
4. While the queue isn't empty: pop a course and do count += 1.
5. For each child of that course: indegree[child] -= 1. If it becomes 0, push the child.
6. Return count == numCourses.

6Code (Python)

from collections import deque

class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]   # parent -> children
        indegree = [0] * numCourses                # how many courses each one waits for

        for course, pre in prerequisites:
            graph[pre].append(course)              # finishing pre helps course
            indegree[course] += 1

        queue = deque()
        for i in range(numCourses):
            if indegree[i] == 0:                   # free right now
                queue.append(i)

        count = 0
        while queue:
            course = queue.popleft()
            count += 1                             # we really took this course
            for child in graph[course]:
                indegree[child] -= 1               # one requirement done
                if indegree[child] == 0:           # nothing left to wait for
                    queue.append(child)

        return count == numCourses

7Code line by line

8Dry run: indegree and queue after every step

n = 5, prerequisites = [[1,0],[0,2],[2,3],[2,4],[3,4]], graph = {0:[1], 1:[], 2:[0], 3:[2], 4:[2,3]}.

 (4✓) ──→ (3:0)
  │         │
  ↓         │
 (2:1) ←────┘
  │
  ↓
 (0:1) ──→ (1:1)

 (4✓) ──→ (3✓)
  │         │
  ↓         │
 (2✓) ←─────┘
  │
  ↓
 (0:0) ──→ (1:1)

 (3✓) ──→ (1:1) ──→ (0:1)
           ↑ │
           │ ↓
           (2:1)
 queue empty, count 1 < 4

9Complexity & remember

The teacher counts each loop separately. Let V = numCourses and E = number of prerequisite pairs:

• Making the empty lists: O(V). Reading the pairs: O(E). Finding the starting zeros: O(V).
• The while loop: each course is popped at most once (V pops), and for each pop we walk its child list. Added up over all courses, the child lists contain each edge once, so that's E steps in total, not V × E.
• Time O(V + E).
• Space O(V + E): the adjacency list stores V lists holding E entries in total. The indegree array and the queue add O(V).

Part B · The same indegree idea with DFS (her comparison)

1The question

The same as Part A. The teacher asks: can we use DFS instead of BFS? Yes. She walks through it to show what changes and why BFS feels more natural here.

2What the constraints tell us

The same numbers, plus one Python-specific danger: DFS uses recursion. If the courses form a straight line 0 → 1 → … → 1999, the recursion goes 2000 calls deep. Python's default limit is about 1000, so it would crash with RecursionError. We raise the limit with sys.setrecursionlimit.

3Intuition

Keep the same rule: you may enter a course only when its indegree hits 0. Instead of putting it in a queue, jump into it immediately (a recursive call), lower its children, and jump into any child that reaches 0.

4Her walkthrough, and the counting trap

The same 5-course example. The free course is 4:

• DFS(4). First child 2: lower it to 1. In her telling, DFS still "visits" 2, but it can't go further because 2 still waits for 3, so it comes straight back.
• Next child 3: lower it to 0 → DFS(3). Its child 2: lower it to 0 → now DFS(2) really goes in.
• DFS(2) → child 0 reaches 0 → DFS(0) → child 1 reaches 0 → DFS(1). Nothing below it, so everything returns.

She counts the calls: 4, 2, 3, 2, 0, 1 = 6 calls for 5 courses, because course 2 was called twice (once too early). So "number of DFS calls" isn't "number of courses taken", and we can't compare it with numCourses.

Her fix: count a course only at the moment its indegree becomes 0 (or collect the taken courses in another structure). In my code I simply don't call DFS on a child until its indegree is 0, so every call is a real "taken" course and I count inside the call.

5Approach steps

1. Build graph and indegree exactly as in Part A.
2. dfs(course): count it, then for each child lower its indegree. If it becomes 0, call dfs(child).
3. Collect the courses whose indegree is 0 at the start, then call dfs on each.
4. Return count == numCourses.

6Code (Python)

import sys

class Solution:
    def canFinish(self, numCourses, prerequisites):
        sys.setrecursionlimit(10000)               # a chain can be 2000 calls deep
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1

        count = 0

        def dfs(course):
            nonlocal count
            count += 1                             # this course is taken
            for child in graph[course]:
                indegree[child] -= 1
                if indegree[child] == 0:           # only enter when it is free
                    dfs(child)

        starts = [i for i in range(numCourses) if indegree[i] == 0]
        for s in starts:
            dfs(s)
        return count == numCourses

7Code line by line

8Dry run: call stack

1. starts = [4]. dfs(4): count 1. Child 2: 2 → 1, so don't enter. Child 3: 1 → 0 → enter.
2. dfs(3): count 2. Child 2: 1 → 0 → enter.
3. dfs(2): count 3. Child 0: 1 → 0 → enter.
4. dfs(0): count 4. Child 1: 1 → 0 → enter.
5. dfs(1): count 5. It has no children, so everything returns.
6. count 5 == 5 → True.

9Complexity & remember

• Time O(V + E): each course is entered once, and each edge is lowered once.
• Space O(V + E): the graph, plus up to V calls on the recursion stack.

Part C · Homework: DFS cycle detection with a path marker

The teacher ends the video by asking us to solve it with DFS ourselves. This is the classic DFS way, using what we learned in Cycle in Directed Graph (DFS).

1The question, restated

"Can all courses be finished?" is the same as "does the directed graph have no cycle?" (Doubt 2 of Part A). So we just run a directed-cycle check.

2What the constraints tell us

The same as Part B: the recursion can be up to 2000 deep, so raise the limit.

3Intuition: the "currently on my path" marker

Walk along the arrows with DFS. Keep a mark on the courses that are on the current path (the call stack right now). If an arrow leads to a course that's still on the current path, we've come round in a loop, which is a cycle.

Each course has 3 states:

4Building the logic

• Use the same adjacency list (pre → course).
• dfs(u): set state 1. For each child: if it's in state 1 → cycle → return False. If it's in state 0 → recurse, and if that found a cycle → return False. State 2 → skip.
• After all children: set state 2 and return True.
• Call it from every course still in state 0, so we cover every separate piece of the graph.

5Approach steps

1. Build the graph. Set state = [0] * n.
2. For each course with state 0: if dfs(course) finds a cycle → return False.
3. If no cycle was found anywhere → return True.

6Code (Python)

import sys

class Solution:
    def canFinish(self, numCourses, prerequisites):
        sys.setrecursionlimit(10000)
        graph = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            graph[pre].append(course)

        state = [0] * numCourses       # 0 = new, 1 = on current path, 2 = done

        def dfs(u):                    # returns False if a cycle is found
            state[u] = 1
            for v in graph[u]:
                if state[v] == 1:      # back to a course still on the path
                    return False
                if state[v] == 0 and not dfs(v):
                    return False
            state[u] = 2               # fully checked, safe
            return True

        for c in range(numCourses):
            if state[c] == 0 and not dfs(c):
                return False
        return True

7Code line by line

8Dry run on the cycle example

n = 4, [[0,1],[1,2],[2,1],[1,3]] → graph = {1:[0, 2], 2:[1], 3:[1], 0:[]}.

1. dfs(0): 0 has no children → state 2.
2. dfs(1): state[1] = 1. Child 0 is already done (state 2), so skip it. Child 2 is new → dfs(2).
3. dfs(2): state[2] = 1. Child 1 has state 1, so it's on the path → cycle → return False.
4. The False goes up through dfs(1) to the main loop → False.

On the 5-course example there's no cycle: every DFS finishes, each course becomes state 2, and the answer is True.

9Complexity & remember

• Time O(V + E): each course turns 0 → 1 → 2 once, and each edge is looked at once.
• Space O(V + E): the graph, the state array and the recursion stack.

Part D · Revision page

s = Solution()
print(s.canFinish(2, [[1, 0]]))                                   # True
print(s.canFinish(2, [[1, 0], [0, 1]]))                           # False
print(s.canFinish(5, [[1, 0], [0, 2], [2, 3], [2, 4], [3, 4]]))   # True
print(s.canFinish(4, [[0, 1], [1, 2], [2, 1], [1, 3]]))           # False
print(s.canFinish(3, []))                                         # True

Based on this video: Course Schedule | Graph · Topological Sort