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?
Approach - Its a graph question, we simply have to find if there is a cycle in the Graph. The graph is directed. We take three sets with names White, Grey and Black. White stores the unvisited nodes, grey stores the visited ones and black stores the node whose all children have been visited. If at any time we encounter a node in grey set, we know that there is a cycle in the graph. Below is the approach but make sure to do yourself first.
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
| import random
class Solution:
def __init__(self):
self.possible = True
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
connections = {}
# visited = set()
if len(prerequisites) == 0:
return True
white = set() #It will store the unvisited nodes
grey = set()#It will store the visited nodes
black = set()#It will store the nodes whose all childrens have beeen visited
for p in prerequisites:
if p[0] not in connections:
connections[p[0]] = set()
connections[p[0]].add(p[1])
white.add(p[0])
white.add(p[1])
# print(white)
def dfs(node,white,grey,black):
if node in grey:
self.possible = False
return
if node in white:
white.remove(node)
grey.add(node)
if node in connections:
for i in connections[node]:
if i not in black:
dfs(i,white,grey,black)
if node in grey:
grey.remove(node)
black.add(node)
while len(white)>0:
node = random.choice(tuple(white))
dfs(node,white,grey,black)
return self.possible
|