[[Graphs]]

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Brainstorming

What is a Topological Sort? The “Getting Dressed” Analogy

Imagine you’re getting dressed in the morning. You have a bunch of clothes: socks, shoes, underwear, pants, shirt, and a jacket.

You know there are rules. You can’t just put them on in any random order.

• You must put on socks before shoes.
• You must put on underwear before pants.
• You must put on a shirt before a jacket.

A topological sort is simply a valid order in which you can put on your clothes.

For example, this is a valid order (a topological sort):
underwear -> pants -> socks -> shirt -> shoes -> jacket

This is also a valid order:
socks -> underwear -> shirt -> pants -> jacket -> shoes

But this is NOT a valid order:
shoes -> socks -> … (You broke a rule!)

So, a topological sort gives you a linear ordering of things that have dependencies.

Now, let’s connect this to graphs.

• The clothes (socks, shoes, etc.) are the vertices.
• The rules (“must do A before B”) are the directed edges. So, you’d have an edge socks -> shoes.

One last crucial question: What if you had a rule A -> B and another rule B -> A? Could you ever get dressed? No! This is a cycle. A topological sort is only possible if there are no cycles. A directed graph with no cycles is called a DAG (Directed Acyclic Graph).

Course Schedule

lets look at the example [0,1] it means to do course 1 we need to to do course 0 , but what about course 0 ? we don’t need to take any course for that

in order to work with graphs we need to first store them , the best way to do so is adjacency list . in this example we can start simple

{0:[1]} here we are representing the key as a course and the value is the the list of courses that depend on it .

what about numCourses = 3 and prerequisites = [[0,1], [1,2]] the adjacency list will look like {0:[1], 1:[2]}

what about numCourses = 2, prerequisites = [[1,0],[0,1]] the adjacency list will be {1:[0], 0:[1]}

but how do we know which is the course that we need to take? also how would we know if the cyclic dependency issue of example 3 ?

to answer this we would need another list where we represent the number of courses required to complete the current course . the best data structure to show this is an array where the index can represent the course for eg index 0 can be course 0 and the value at the index can be the number of courses required to complete that course we can show this for our examples

[0,1] adjacency list {0:[1]} pre_req_list = [0,1] [[0,1], [1,2]] adjacency list = {0:[1], 1:[2]} pre_req_list = [0,1,1] [[1,0], [0,1]] adjacency list = {1:[0], 0:[1]} pre_req_list = [1,1]

this idea of a prerequisite list is pretty powerful as it solved 2 problems

1. how many courses do we need to finish before we can take the current course
2. if there are courses that depend on each other?

but how does it all come together now?

the good starting point would be to put together all the courses that we can take at the start which have no pre requisite and add them to a queue for processing

from collections import deque
queue = deque()
for index, i in enumerat(pre_req_list):
	if i == 0:
		queue.append(index)	
		

now we will start processing this queue till the time its not empty using a while loop but what does processing look like

1. we need to take the course i.e pop it from the queue
2. then we need to find its dependent course we can do that with our adjacency list
3. now for this list of neighbours we go one by one and delete 1 course requirement from the pre requisite array
4. if after this course taking we find that all the pre requistes are satisfied i.e the value of the course index is 0 that means that course is ready to be taken hence we add it to the queue for processing

while queue:
	course = queue.pop()
	result.append(course) # take the course
	dependent_courses = adjacency_list[course]
	for course in dependent_courses:
		pre_req_list[course] -=1
		if pre_req_list[course] == 0:
			queue.append(course)

now for the cyclic dependencies if the result array is empty it will be clear that there are cycles in the graph hence topological sort is not possible. How , well if you see the first step where we try to get all the pre-requisite courses in the first pass in cyclic graphs this queue will never get formed hence the remaining algorithm will not even being so the final test we have to do is

return if result 

In that specific scenario, the queue never gets anything added to it, the loop never runs, and the result list is indeed empty.

But let’s consider a slightly trickier case. What if a cycle exists, but not all courses are part of it?

Consider numCourses = 3 and prerequisites =[[0,1], [1,2], [2,1]]

• Course 0 is a valid starting course.
• But there is a cycle between Course 1 and Course 2.

Let’s trace your algorithm:

1. Setup:

   • adjacency_list = {0: [1], 1: [2], 2: [1]}
   • pre_req_list = [0, 2, 1] (Course 1 needs 2 prereqs, Course 2 needs 1)

2. Initialization:

   • You scan pre_req_list. The only course with 0 prereqs is Course 0.
   • queue becomes [0].

3. Loop starts:

   • course = 0 is popped from the queue.
   • result becomes [0].
   • The dependent course is 1. You update its pre-req count: pre_req_list[1] becomes 2 - 1 = 1.
   • Since the count for 1 is not 0, it is not added to the queue.

4. End of loop: The queue is now empty. The loop terminates.

What is your final result list? It’s [0]. It is not empty!

But did we succeed? No. We only managed to take 1 out of the 3 courses. We got stuck because the remaining courses, 1 and 2, are locked in a cycle, forever waiting for each other.

So, the condition is not just about the result being empty. It’s about whether the result contains everything it should.

The real test is:

Did the number of courses we were able to take (len(result)) equal the total number of courses we were supposed to take (numCourses)?

Therefore, the final line should be:

return len(result) == numCourses

putting everything together

from collections import deque , defaultdict

numCourses = 3
prequisites = [[0,1], [1,2]]
result = []
adjaency_list = defaultdict(list)

# create the adjancency list
for course1 , course2 in prequisites:
	adjaency_list[course1].append(course2)

# Step 1: Start with a list of all zeros.
pre_req_list = [0] * numCourses

# Step 2 & 3: Read the rules and update the counts.
# For a rule like [A, B], it's Course B that has the prerequisite.
for prereq, course in prerequisites:
    pre_req_list[course] += 1
	

queue = deque()
for index, i in enumerate(pre_req_list):
	if i == 0:
		queue.append(index)	


while queue:
	course = queue.popleft()
	result.append(course) # take the course
	dependent_courses = adjacency_list[course]
	for course in dependent_courses:
		pre_req_list[course] -=1
		if pre_req_list[course] == 0:
			queue.append(course)

print(len(result) == numCourses)

Ideal version

from collections import deque, defaultdict

numCourses = 3
prerequisites = [[0,1], [1,2]]
result = []

# --- Data Structure Setup ---

# Using the corrected variable name
adjacency_list = defaultdict(list)
# Initialize the prerequisite counter list with all zeros
pre_req_list = [0] * numCourses

# Create the adjacency list AND the prerequisite list in the same loop
for prereq, course in prerequisites:
    adjacency_list[prereq].append(course)
    pre_req_list[course] += 1 # Increment the count for the course that has the prereq

# --- Kahn's Algorithm ---

# Find the starting courses (those with 0 prerequisites)
queue = deque()
# Using the corrected 'enumerate'
for index, count in enumerate(pre_req_list):
    if count == 0:
        queue.append(index)

# Process the courses
while queue:
    # Use popleft() for First-In, First-Out behavior
    course = queue.popleft()
    result.append(course) # "Take" the course

    # If this course was a prerequisite for other courses...
    if course in adjacency_list:
        dependent_courses = adjacency_list[course]
        for dependent in dependent_courses:
            # ...decrement their prerequisite count
            pre_req_list[dependent] -= 1
            # If a dependent course now has 0 prereqs, it's ready to be taken
            if pre_req_list[dependent] == 0:
                queue.append(dependent)

# --- Final Check ---
print(f"Is it possible to finish all courses? {len(result) == numCourses}")
# Let's also see the valid order:
print(f"A valid order to take the courses is: {result}")