Course Schedule - leetcode 207 and 210 using python

207. Course Schedule

leetcode

Key Idea

Create graph from given prerequisites, and then check if cycles exist in the graph.
If any cycle exist, taking all courses is impossible.

Using topological sort by DFS or BFS, checking cycles is possible. See this post

Use DFS

In [7]:

from collections import defaultdict

class Solution(object):
    def __init__(self):
        self.isDAG = True

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        adj = defaultdict(list)
        for i, j in prerequisites:
            adj[j].append(i)

        seen = [False] * numCourses
        finish = [False] * numCourses
        topo = []

        def dfs(i):
            seen[i] = True
            for j in adj[i]:
                if not seen[j]:
                    dfs(j)
                elif not finish[j]:
                    self.isDAG = False
            finish[i] = True
            topo.append(i)

        for i in range(numCourses):
            if not seen[i]:
                dfs(i)
        if not self.isDAG:
            return False
        else:
            return len(topo) == numCourses

In [8]:

numCourses = 2
prerequisites = [[0, 1]]
sol = Solution()
print(sol.canFinish(numCourses, prerequisites))

True

Use BFS

In [4]:

from collections import defaultdict, deque

class Solution(object):
    def __init__(self):
        self.isDAG = True

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        adj = defaultdict(list)
        indegree = [0] * numCourses
        for i, j in prerequisites:
            adj[j].append(i)
            indegree[i] += 1
        
        st = [i for i in range(numCourses) if indegree[i] == 0]
        queue = deque(st)
        cnt = 0
        while queue:
            i = queue.popleft()
            for j in adj[i]:
                indegree[j] -= 1
                if indegree[j] == 0:
                    queue.append(j)
            cnt += 1
        return cnt == numCourses

In [5]:

numCourses = 2
prerequisites = [[0, 1]]
sol = Solution()
print(sol.canFinish(numCourses, prerequisites))

True

210. Course Schedule II

DFS

In [11]:

from collections import defaultdict
class Solution(object):
    def __init__(self):
        self.isDAG = True
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        adj = defaultdict(list)
        for i, j in prerequisites:
            adj[j].append(i)
        seen = [False]*numCourses
        finish = [False]*numCourses
        topo = []
        def dfs(i):
            seen[i] = True
            for j in adj[i]:
                if not seen[j]:
                    dfs(j)
                elif not finish[j]:
                    self.isDAG = False
            finish[i] = True
            topo.append(i)
        for i in range(numCourses):
            if not seen[i]:
                dfs(i)
        if not self.isDAG:
            return []
        else:
            return topo[::-1]

sol = Solution()

In [12]:

sol.findOrder(numCourses, prerequisites)

[1, 0]

BFS

In [13]:

from collections import defaultdict, deque
class Solution(object):
    def __init__(self):
        self.isDAG = True
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        adj = defaultdict(list)
        indegree = [0]* numCourses
        for i, j in prerequisites:
            adj[j].append(i)
            indegree[i] += 1
        
        st = [i for i in range(numCourses) if indegree[i] == 0]    
        queue = deque(st)
        cnt, topo = 0, []
        while queue:
            i = queue.popleft()
            topo.append(i)
            for j in adj[i]:
                indegree[j] -= 1
                if indegree[j] == 0:
                    queue.append(j)
            cnt += 1
        
        if cnt != numCourses:
            return []
        else:
            return topo

In [14]:

sol.findOrder(numCourses, prerequisites)

[1, 0]