卖萌的弱渣

I am stupid, I am hungry.

Course Schedule

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

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example:

  • 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

  • 2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Solution

  • Idea is posted in “Course Schedule II”
(Course-Schedule.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        if prerequisites == None:
            return True
        course = [x for x in range(numCourses)]
        hash_map = [0]*numCourses # out-degree of each node
        children = [[] for x in range(numCourses)] # children set of each node
        # init hash_map and children
        for i,j in prerequisites:
            hash_map[i] += 1
            children[j].append(i)

        while len(course) != 0:
            # find the node without outdegree
            remove_list = []
            flag = False
            for x in course:
                # find pre-course
                if hash_map[x] == 0:
                    # update hash_map
                    for child in children[x]:
                        hash_map[child] -= 1
                    flag = True
                    remove_list.append(x)

            if flag == False:
                return False

            for x in remove_list:
                course.remove(x)
        return True