leetcode-py/2015/CourseSchedule_v1.py at master · everbird/leetcode-py · 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
#!/usr/bin/env python
# encoding: utf-8


class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        g = [0] * numCourses
        d = []
        for i in range(numCourses):
            d.append([])

        for f, t in prerequisites:
            d[f].append(t)

        for i in range(numCourses):
            if not self.dfs(g, d, i):
                return False

        return True

    def dfs(self, g, d, start):
        if g[start] == -1:
            return False
        elif g[start] == 1:
            return True
        g[start] = -1
        for i in d[start]:
            if not self.dfs(g, d, i):
                return False

        g[start] = 1
        return True


if __name__ == '__main__':
    s = Solution()
    print s.canFinish(2, [[1,0]])
    print s.canFinish(2, [[1,0],[0,1]])