course_schedule_ii
1from collections import defaultdict, deque 2 3 4# @leet start 5class Solution: 6 def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]: 7 """ 8 This function finds an ordering of a graph given that some nodes have 9 dependencies. 10 11 We first iterate through the prerequisites by adding each course's 12 prerequisites to a dictionary that lists its indegrees (each course requires 13 these prerequisites) and its outdegrees (where each prereq lists which 14 courses it is required for) 15 16 Then we populate a queue with the nodes without indegrees (no prerequisites) 17 18 And then, for each node in the queue, we complete its courses, by looking 19 at each of its outdegrees, and then checking to see if that course has 20 no more dependencies by checking that course's indegrees. 21 22 If that's the case, we add the course we're checking to the queue and 23 continue on. 24 25 We have a valid ordering if we can visit all nodes. If we cannot, there is 26 a cycle and no topological ordering. 27 """ 28 indegrees = defaultdict(set) 29 outdegrees = defaultdict(set) 30 for course, prereq in prerequisites: 31 indegrees[course].add(prereq) 32 outdegrees[prereq].add(course) 33 34 q = deque([c for c in range(numCourses) if c not in indegrees]) 35 36 schedule = [] 37 38 while q: 39 course = q.popleft() 40 schedule.append(course) 41 42 for outdegree in outdegrees[course]: 43 indegrees[outdegree].remove(course) 44 if not indegrees[outdegree]: 45 q.append(outdegree) 46 47 return schedule if len(schedule) == numCourses else [] 48 49 50# @leet end 51 52 53def test(): 54 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]: 8 """ 9 This function finds an ordering of a graph given that some nodes have 10 dependencies. 11 12 We first iterate through the prerequisites by adding each course's 13 prerequisites to a dictionary that lists its indegrees (each course requires 14 these prerequisites) and its outdegrees (where each prereq lists which 15 courses it is required for) 16 17 Then we populate a queue with the nodes without indegrees (no prerequisites) 18 19 And then, for each node in the queue, we complete its courses, by looking 20 at each of its outdegrees, and then checking to see if that course has 21 no more dependencies by checking that course's indegrees. 22 23 If that's the case, we add the course we're checking to the queue and 24 continue on. 25 26 We have a valid ordering if we can visit all nodes. If we cannot, there is 27 a cycle and no topological ordering. 28 """ 29 indegrees = defaultdict(set) 30 outdegrees = defaultdict(set) 31 for course, prereq in prerequisites: 32 indegrees[course].add(prereq) 33 outdegrees[prereq].add(course) 34 35 q = deque([c for c in range(numCourses) if c not in indegrees]) 36 37 schedule = [] 38 39 while q: 40 course = q.popleft() 41 schedule.append(course) 42 43 for outdegree in outdegrees[course]: 44 indegrees[outdegree].remove(course) 45 if not indegrees[outdegree]: 46 q.append(outdegree) 47 48 return schedule if len(schedule) == numCourses else []
def
findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
7 def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]: 8 """ 9 This function finds an ordering of a graph given that some nodes have 10 dependencies. 11 12 We first iterate through the prerequisites by adding each course's 13 prerequisites to a dictionary that lists its indegrees (each course requires 14 these prerequisites) and its outdegrees (where each prereq lists which 15 courses it is required for) 16 17 Then we populate a queue with the nodes without indegrees (no prerequisites) 18 19 And then, for each node in the queue, we complete its courses, by looking 20 at each of its outdegrees, and then checking to see if that course has 21 no more dependencies by checking that course's indegrees. 22 23 If that's the case, we add the course we're checking to the queue and 24 continue on. 25 26 We have a valid ordering if we can visit all nodes. If we cannot, there is 27 a cycle and no topological ordering. 28 """ 29 indegrees = defaultdict(set) 30 outdegrees = defaultdict(set) 31 for course, prereq in prerequisites: 32 indegrees[course].add(prereq) 33 outdegrees[prereq].add(course) 34 35 q = deque([c for c in range(numCourses) if c not in indegrees]) 36 37 schedule = [] 38 39 while q: 40 course = q.popleft() 41 schedule.append(course) 42 43 for outdegree in outdegrees[course]: 44 indegrees[outdegree].remove(course) 45 if not indegrees[outdegree]: 46 q.append(outdegree) 47 48 return schedule if len(schedule) == numCourses else []
This function finds an ordering of a graph given that some nodes have dependencies.
We first iterate through the prerequisites by adding each course's prerequisites to a dictionary that lists its indegrees (each course requires these prerequisites) and its outdegrees (where each prereq lists which courses it is required for)
Then we populate a queue with the nodes without indegrees (no prerequisites)
And then, for each node in the queue, we complete its courses, by looking at each of its outdegrees, and then checking to see if that course has no more dependencies by checking that course's indegrees.
If that's the case, we add the course we're checking to the queue and continue on.
We have a valid ordering if we can visit all nodes. If we cannot, there is a cycle and no topological ordering.
def
test():