Simple python solution with detailed comments

  • 0
    class Solution(object):
    	def canFinish(self, numCourses, prerequisites):
    		:type numCourses: int
    		:type prerequisites: List[List[int]]
    		:rtype: bool
    		# adjacency linked list
    		adjacency_linked_list = {}
    		# quickly access number of incoming edges
    		incoming_edges_counter = [0] * numCourses
    		for prerequisite, course in prerequisites:
    			if prerequisite not in adjacency_linked_list:
    				adjacency_linked_list[prerequisite] = set()
    			incoming_edges_counter[course] += 1
    		# create set of courses which have satisfied all the prerequisites
    		prerequisite_free_courses = set()
    		for i in range(numCourses):
    			if incoming_edges_counter[i] == 0:
    		# count number of courses completed as there was no prerequisite for them
    		courses_completed = 0
    		while prerequisite_free_courses:
    			# temporary set for next set of prerequisite free courses
    			tmp = set()
    			# find out new prerequisite free courses if we take all the courses which did not have prerequisites
    			for course in prerequisite_free_courses:
    				courses_completed += 1
    				for course_with_prerequisite in adjacency_linked_list[course]:
    					incoming_edges_counter[course_with_prerequisite] -= 1
    					if incoming_edges_counter[course_with_prerequisite] == 0:
    			prerequisite_free_courses = tmp
    		# return results if is possible to complete all the courses
    		if courses_completed == numCourses:
    			return True
    			return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.