207.md

Courses Schedule

Description

link

---

Solution1 : BFS

• Vars
  • graph: store edges
  • in_degrees: numbers of degrees to be learned
  • q: courses ready for learning
  • visited: unique courses have learned
• steps
  • set all variables
  • put all in_degrees == 0 course into q, which means we can choose these courses at any time
  • q.popleft(), learn the first course and cut 1 from the in_degree[i]
  • record courses have visited

Thinking:

Why we can just cut 1 from all in_degree[i] and dont worry about the duplicates courses learned?

In fact we can do that:

if g in visited:
    pass

But we can imagine that if a node is in q, means from graph there is no way to get into it from edge, this is a method so called Topological Sorting

---

Code 1

Complexity T : O(V + E) M : O(V + E)

class Solution:
    def canFinish(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        # construct graph
        graph = {i: set() for i in range(n)}
        in_degrees = {i:0 for i in range(n)}
        
        for edge in edges:
            graph[edge[0]].add(edge[1])
            in_degrees[edge[1]] += 1
        
        # init var 
        q = collections.deque()
        visited = set()
        
        # find nodes whose in degree == 0
        for index, in_degree in in_degrees.items():
            if in_degree == 0:
                q.append(index)
                
        # loop all nodes whose in degree == 0
        while q:
            index = q.popleft()
            visited.add(index)
            for g in graph[index]:
                in_degrees[g] -= 1
                if in_degrees[g] == 0:
                    q.append(g)
        return len(visited) == n

Solution1 : DFS + Find cycle

It is more easier to understand in dfs solution

visited or status to record the status of node i

• -1 means it has been visited before, return False (Find a cycle)
• 0 means it has not been visited before, visited all its neighbors and mark it
• 1 means all its neighbors' status is ok, return True

return if all nodes can find a no-cycle way to get out

---

Code 2

Complexity T : O(VE) worst situation

class Solution(object):
    def canFinish(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        pre = collections.defaultdict(list)
        for x, y in edges: pre[x].append(y)

        status = [0] * n
        def canTake(i):
            if status[i] in {1, -1}: return status[i] == 1
            status[i] = -1
            if any(not canTake(j) for j in pre[i]): return False
            status[i] = 1
            return True

        return all(canTake(i) for i in range(n))


# More readable code:
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        graph = [[] for _ in range(numCourses)]
        visited = [0 for _ in range(numCourses)]
        # create graph
        for pair in prerequisites:
            x, y = pair
            graph[x].append(y)
        # visit each node
        for i in range(numCourses):
            if not self.dfs(graph, visited, i):
                return False
        return True
    
    def dfs(self, graph, visited, i):
        # if ith node is marked as being visited, then a cycle is found
        if visited[i] == -1:
            return False
        # if it is done visted, then do not visit again
        if visited[i] == 1:
            return True
        # mark as being visited
        visited[i] = -1
        # visit all the neighbours
        for j in graph[i]:
            if not self.dfs(graph, visited, j):
                return False
        # after visit all the neighbours, mark it as done visited
        visited[i] = 1
        return True