210. Course Schedule II

There are a total of n courses you have to take labelled from 0 to n - 1.

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

My Answer 1: Accepted (Runtime: 96 ms - 83.55% / Memory Usage: 17.7 MB - 11.08%)

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: 
        result = []
        
        graph = {i:[] for i in range(numCourses)}
        for course,pre_course in prerequisites:
            graph[course].append(pre_course)
            
        # whether exist circle
        def DFS(course,seen):
            # if node have been traveled
            if seen[course]==0:
                return False
            elif seen[course]==1:
                return True
            
            seen[course] = 1
            for pre_course in graph[course]:
                if DFS(pre_course,seen):
                    seen[course] = 0
                    return True
            seen[course] = 0
            
            result.append(course)
            return False
			
        seen = {i:-1 for i in range(numCourses)}    
        for course in range(numCourses):
            if DFS(course,seen):
                return []
        
        return result

저번에 푼 Course Schedule I 에서 사용한 DFS 를 응용해야겠구나 함

DFS 함수 돌면서 result.append(course) 를 추가해줬다
graph[course] 값을 타고타서 가기 때문에 순서대로 result 에 들어감

사실 100퍼 이해는 안된다는 점~..^^

TOPOLOGICAL SORT

Solution 1: Runtime: 176 ms - 9.85% / Memory Usage: 18 MB - 7.88%

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        ## RC ##
        ## APPROACH : TOPOLOGICAL SORT ##
        ## Similar to 207. Course Schedule ##
        
		## TIME COMPLEXITY : O(N) ##
		## SPACE COMPLEXITY : O(N) ##
        
        def hasCycle(node):
            if(node in exploring): return True
            if(node in explored): return False
            exploring.add(node)                         
            for nei in graph[node]:                     
                if( hasCycle(nei) ):
                    return True          
            explored.add(node)
            result.append(node)
            exploring.remove(node)
            return False
        
        graph = collections.defaultdict(list)
        for u,v in prerequisites:       
            graph[v].append(u)              # v -> u
        
        result = []
        explored = set()                                 
        exploring = set()                                
        for node in range(numCourses):      # range(numCourses)  
            if(node not in explored):
                if( hasCycle(node) ):         
                    return []
        return result[::-1]

TOPOLOGICAL SORT 를 쓰는 사람이 꽤 많았다...