Simple python solution with detailed comments


  • 0
    S
    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()
    
    			adjacency_linked_list[prerequisite].add(course)
    			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:
    				prerequisite_free_courses.add(i)
    		
    		# 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:
    						tmp.add(course_with_prerequisite)
    			prerequisite_free_courses = tmp
    		
    		# return results if is possible to complete all the courses
    		if courses_completed == numCourses:
    			return True
    		else:
    			return False
    

Log in to reply
 

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