LeetCode/courseScheduleII.py at master · Yorktsc/LeetCode · GitHub

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from collections import defaultdict
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        m = defaultdict(list)
        queue = [i for i in range(numCourses)]
        seen = set(queue)
        for course, preq in prerequisites:
            if course in seen:
                queue.remove(course)
                seen.remove(course)
            m[course].append(preq)
        flag = True
        while flag:
            flag = False
            for c, preqs in m.items():
                tmp = preqs[:]
                for p in preqs:
                    if p in seen:
                        tmp.remove(p)
                m[c] = tmp
                if len(m[c]) == 0:
                    queue.append(c)
                    seen.add(c)
                    del m[c]
                    flag = True
        if len(queue) == numCourses:
            return queue
        return []

        """
        in_degree = {i:0 for i in range(numCourses)}
        graph = {i:set() for i in range(numCourses)}
        for c,p in prerequisites:
            graph[p].add(c)
            in_degree[c] += 1
        stack, res = [], []
        for c, d in in_degree.items():
            if d == 0:
                stack.append(c)
        while stack:
            node = stack.pop(-1)
            res.append(node)
            for i in graph[node]:
                in_degree[i] -= 1
                if in_degree[i] == 0:
                    stack.append(i)
        return [] if len(res) != numCourses else res
        """