# Week 6 Session 1 Solutions
## [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)

from collections import defaultdict

class Solution:
    UNVISITED = 0
    VISITING = 1
    VISITED = 2

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = self.buildGraph(prerequisites)
        state = [Solution.UNVISITED] * numCourses
        ordering = []
        
        for course in range(numCourses):
            if state[course] == Solution.UNVISITED:
                isPossible = self.dfs(course, graph, state, ordering)
                if not isPossible:
                    return []
        
        return reversed(ordering)

    def dfs(self, course, graph, state, ordering):
        state[course] = Solution.VISITING
        
        for neighbor in graph[course]:
            if state[neighbor] == Solution.UNVISITED:
                isPossible = self.dfs(neighbor, graph, state, ordering)
                if not isPossible:
                    return False
            elif state[neighbor] == Solution.VISITING:
                return False
        
        state[course] = Solution.VISITED
        ordering.append(course)
        return True
    
    def buildGraph(self, prerequisites):
        graph = defaultdict(set)
        for (course, prerequisite) in prerequisites:
            graph[prerequisite].add(course)
        return graph

## [Find Eventual Safe States](https://leetcode.com/problems/find-eventual-safe-states)

class Solution:
    UNVISITED = 0
    VISITING = 1
    SAFE = 3
    UNSAFE = 4
    
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        numNodes = len(graph)
        state = [Solution.UNVISITED] * numNodes
        for node in range(numNodes):
            if state[node] == Solution.UNVISITED:
                self.dfs(graph, node, state)
        safeNodes = []
        for (i, nodeState) in enumerate(state):
            if nodeState == Solution.SAFE:
                safeNodes.append(i)
        return safeNodes
    
    def dfs(self, graph, currNode, state):
        if state[currNode] == Solution.SAFE:
            return True
        if state[currNode] == Solution.VISITING or state[currNode] == Solution.UNSAFE:
            return False
        state[currNode] = Solution.VISITING
        isSafe = True
        for neighbor in graph[currNode]:
            isSafe &= self.dfs(graph, neighbor, state)
            if not isSafe:
                break
        state[currNode] = Solution.SAFE if isSafe else Solution.UNSAFE
        return isSafe