PythonAlgorithms/ColouredCycleDetecDir.py at master · IKMalik/PythonAlgorithms · 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
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        if prerequisites is None:
            return True

        graph = {}

        for key in range(numCourses):
            graph[key] = []

        for pre in prerequisites:

            start, end = pre
            graph[start].append(end)

        # white = unvisited = 0
        colours = [0 for _ in range(numCourses)]

        for course in range(numCourses):
            if colours[course] == 0:
                if self.isCyclic(course, graph, colours) == True: # if cycle is found
                    return False
        return True

    def isCyclic(self, course, graph, colours):

        # grey = visiting = 1
        colours[course] = 1

        for neighbour in graph[course]:

            # Cycle found
            if colours[neighbour] == 1:
                return True

            if colours[neighbour] == 0 and self.isCyclic(neighbour, graph, colours) == True:
                return True

        # black = visited = -1
        colours[course] = -1
        return False