forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
course-schedule-ii.py
60 lines (55 loc) · 1.81 KB
/
course-schedule-ii.py
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
55
56
57
58
59
60
# Time: O(|V| + |E|)
# Space: O(|E|)
import collections
# bfs solution
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
in_degree = collections.defaultdict(set)
out_degree = collections.defaultdict(set)
for i, j in prerequisites:
in_degree[i].add(j)
out_degree[j].add(i)
q = collections.deque([i for i in xrange(numCourses) if i not in in_degree])
result = []
while q:
node = q.popleft()
result.append(node)
for i in out_degree[node]:
in_degree[i].remove(node)
if not in_degree[i]:
q.append(i)
del in_degree[i]
del out_degree[node]
return result if not in_degree and not out_degree else []
# Time: O(|V| + |E|)
# Space: O(|E|)
# dfs solution
class Solution2(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
in_degree = collections.defaultdict(set)
out_degree = collections.defaultdict(set)
for i, j in prerequisites:
in_degree[i].add(j)
out_degree[j].add(i)
stk = [i for i in xrange(numCourses) if i not in in_degree]
result = []
while stk:
node = stk.pop()
result.append(node)
for i in out_degree[node]:
in_degree[i].remove(node)
if not in_degree[i]:
stk.append(i)
del in_degree[i]
del out_degree[node]
return result if not in_degree and not out_degree else []