**Solution**

**Course Schedule** https://leetcode.com/problems/course-schedule/

**3 State Array Solution using DFS: O(V + E)**

- We just need to detect a cycle in this problem. The algorithm we use is a variant of DFS where we color the node as 0(unvisited), 1(visiting), and 2(visited). We can maintain a state array to maintain the status of the nodes. While doing a DFS for a node X, we mark it as visiting (1). Before we complete the DFS for this node, if we encounter a back-edge, i.e. another node Y with neighbor X, we detect a cycle.

```
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
graph = {}
for v in range(numCourses):
graph[v] = []
for pre in prerequisites:
graph[pre[0]].append(pre[1])
return not self.detect_cycle(graph, numCourses)
def detect_cycle(self, g, n):
state = [0]*n
for i in range(n):
if state[i] == 0: # If the node is unvisited.
if self.detect(g, i, state):
return True
return False
def detect(self, g, i, state):
state[i] = 1 # Mark the node in visiting status.
for nbr in g[i]:
if state[nbr] == 1: # We found a back edge! Return True.
return True
elif state[nbr] == 0: # Do DFS only if you find an unvisited neighbor
if self.detect(g, nbr, state):
return True
state[i] = 2 # Mark the node as visited
return False
```

**Visited and Visiting Set Solution using DFS: O(V+E)**

- Now we can implement this algorithm using 2 sets: visiting and visited.
- Notice the choice of API. detect_cycle will return T for a cycle & F for no cycle.
- Just remember to remove the node from visiting after you have completed DFS. Example; 2, [1,0]. You will start with node 0 and add to visiting but not remove it. Then when you start with node 1, you will find its neighbor node 0 in visiting set and incorrectly mark a cycle.
- Note when we call detect recursively within detect, we do collect its output result and process it appropriately.

```
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
graph = {}
for v in range(numCourses):
graph[v] = []
for pre in prerequisites:
graph[pre[0]].append(pre[1])
return not self.detect_cycle(graph, numCourses)
def detect_cycle(self, g, n):
visiting, visited = set([]), set([])
for i in range(n):
if i not in visited:
if self.detect(g, i, visiting, visited):
return True
return False
def detect(self, g, i, visiting, visited):
visited.add(i)
visiting.add(i)
for nbr in g[i]:
if nbr in visiting:
return True
elif nbr not in visited:
if self.detect(g, nbr, visiting, visited):
return True
visiting.remove(i)
return False
```