Python BFS solution


  • 0
    M

    I built two dictionaries, one is to store edges, another is to store dependencies. then start from an node without dependencies and start breath-first-search, pushing each vertex into a queue if this vertex does not have any dependency, meanwhile, update node dependencies dict which depends on it.

    class Solution(object):
    	def findOrder(self, numCourses, prerequisites):
    		"""
    		:type numCourses: int
    		:type prerequisites: List[List[int]]
    		:rtype: List[int]
    		"""
    		maps = collections.defaultdict(list)
    		dependency = collections.defaultdict(list)
    		visited = set()
    		queue = []
    		for i in range(0, numCourses):
    			maps[i] = []
    		for [c, d] in prerequisites:
    			maps[d] += c,
    			dependency[c] += d,
    		startpoints = [x for x in maps if x not in dependency]
    		i = 0
    		for key in startpoints:
    			if key not in visited:
    				queue += key,
    				visited.add(queue)
    				for child in maps[key]:
    					dependency[child].remove(key)
    			while i < len(queue):
    				for child in maps[queue[i]]:
    					if child not in visited and not dependency[child]:
    						queue += child,
    						visited.add(child)
    						for dchild in maps[child]:
    							dependency[dchild].remove()
    				i += 1
    		if len(queue) == numCourses:
    			return queue
    		else:
    			return []
    

Log in to reply
 

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