# Python 20 lines DFS solution sharing with explanation

• ``````def canFinish(self, numCourses, prerequisites):
graph = [[] for _ in xrange(numCourses)]
visit = [0 for _ in xrange(numCourses)]
for x, y in prerequisites:
graph[x].append(y)
def dfs(i):
if visit[i] == -1:
return False
if visit[i] == 1:
return True
visit[i] = -1
for j in graph[i]:
if not dfs(j):
return False
visit[i] = 1
return True
for i in xrange(numCourses):
if not dfs(i):
return False
return True
``````
1. if node `v` has not been visited, then mark it as `0`.
2. if node `v` is being visited, then mark it as `-1`. If we find a vertex marked as `-1` in DFS, then their is a ring.
3. if node `v` has been visited, then mark it as `1`. If a vertex was marked as `1`, then no ring contains `v` or its successors.

References: daoluan.net

• great idea ! thanks for sharing

• at the first glance, i think u can use memo to improve, however, when i realize that u use visit array as implicit memo i know this is a great trick, thanks~

• @rodolphe Could be cleaner code. Check this out.

``````class Solution(object):
def canFinish(self, n, edges):
graph = {i:set() for i in range(n)}
indeg = {i:0     for i in range(n)}
for s, e in set(tuple(x) for x in edges):
graph[s] |= {e}
indeg[e] += 1
queue  =  [i for i in range(n) if not indeg[i]]
visits =  set(queue)
for node in queue:
for neigh in graph[node]:
if neigh in visits:
return False
indeg[neigh] -= 1
if not indeg[neigh]:
queue += neigh,
return len(visits) == n
``````

• This solution might be longer, but it is slightly easier to read. Comments are in-line. Thanks.

``````class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
graph = [[] for _ in range(numCourses)]
visited = [0 for _ in range(numCourses)]
# create graph
for pair in prerequisites:
x, y = pair
graph[x].append(y)
# visit each node
for i in range(numCourses):
if not self.dfs(graph, visited, i):
return False
return True

def dfs(self, graph, visited, i):
# if ith node is marked as being visited, then a cycle is found
if visited[i] == -1:
return False
# if it is done visted, then do not visit again
if visited[i] == 1:
return True
# mark as being visited
visited[i] = -1
# visit all the neighbours
for j in graph[i]:
if not self.dfs(graph, visited, j):
return False
# after visit all the neighbours, mark it as done visited
visited[i] = 1
return True

``````

• @hanfang.cshl
why you do have to use -1 , 1 and 0 in visited array?
In other words,
Why do you divide it into being visited, visiting neighbours, done visited?
Is there any way to use 1 or 0 in the visited array to solve this problem?

• @rodolphe Nice DFS algorithm! A small modification is possible, though:
the last four lines can be combined into

``````return all(dfs(i) for i in xrange(numCourses))
``````

• @agave Very cool! But i think what you described is Kahn's algorithm, not DFS... https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm

• @Zura -1 means this node is part of the current trip. if you see it again, it's a cycle. 1 means a dfs has been done starting from this node, and no cycle was found. if you hit this, going down this path won't find any cycles

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.