# BFS
def findOrder1(self, numCourses, prerequisites):
dic = {i: set() for i in xrange(numCourses)}
neigh = collections.defaultdict(set)
for i, j in prerequisites:
dic[i].add(j)
neigh[j].add(i)
# queue stores the courses which have no prerequisites
queue = collections.deque([i for i in dic if not dic[i]])
count, res = 0, []
while queue:
node = queue.popleft()
res.append(node)
count += 1
for i in neigh[node]:
dic[i].remove(node)
if not dic[i]:
queue.append(i)
return res if count == numCourses else []
# DFS
def findOrder(self, numCourses, prerequisites):
dic = collections.defaultdict(set)
neigh = collections.defaultdict(set)
for i, j in prerequisites:
dic[i].add(j)
neigh[j].add(i)
stack = [i for i in xrange(numCourses) if not dic[i]]
res = []
while stack:
node = stack.pop()
res.append(node)
for i in neigh[node]:
dic[i].remove(node)
if not dic[i]:
stack.append(i)
dic.pop(node)
return res if not dic else []
Python dfs, bfs solutions with comments.


@caikehe I wouldn't say it's DFS since you're going through the neighbors and then adding into the stack. Still looks like BFS to me
for i in neigh[node]: dic[i].remove(node) if not dic[i]: stack.append(i)

@livelearn
Stack(FILO) and pop() function pops out the last item in the array. Although the neighbors( "i in neigh[node]" ) are added into stack that looks like DFS, but they won't be pop out in the same order. For example, if we have "dic", "neigh" and "stack" like this:
dic = { 3: [1,2], 4: [2,3]}, neigh = {1: [3], 2: [3, 4], 3: [4] } and stack = [0,1,2]
1st iteration:
node = 2, res = [2], dic = {3: [1], 4:[3]}, neigh = {1: [3], 2: [3, 4], 3: [4] } , stack = [0, 1]
2nd iteration:
node = 1, res[2, 1], dic = {4:[3]},neigh = {1: [3], 2: [3, 4], 3: [4] } , stack = [0, 3]
3rd iteration:
node = 3, res[2,1,3], dict = {}, neigh = {1: [3], 2: [3, 4], 3: [4] } , stack = [0, 4]
// Here, node 3 is the child of node 1, and it's been taken right after node 1 since it's pop from a stack(last in first out). It means that as long as the child node meets the condition that no prerequisite is required or all the prerequisite has been taken, this child node will be added to the result and it's children will be added to the stack. So the next to be visited is node 4  the child of node 3.
Thus, the final effect is still dfs, although not the normal dfs in our common sense. It's like always going to the next level through the last child (or the right most leaf if you are more familiar the tree structure), instead of the first child it reaches directly (or the left most leaf).
It's just my thought, and I hope it makes sense. Please let me know if I made anything wrong here. :)

@sha256pki If the tree contains cycle, the returned dictionary
dic
would not be empty. Therefore the dfs function will return[]

nice solution, however I think dic[i] should be the indegree of the node i, then computing will be faster !!
class Solution(object): def findOrder(self, numCourses, prerequisites): # dic[i] is the indegree of the node i, computing will be faster dic = [0 for i in xrange(numCourses)]; neigh = collections.defaultdict(set) for i, j in prerequisites: dic[i] += 1; neigh[j].add(i) stack = [i for i in xrange(numCourses) if dic[i] == 0]; res = [] while stack: node = stack.pop() res.append(node) for i in neigh[node]: dic[i] = 1 if dic[i] == 0: stack.append(i) for i in xrange(numCourses): if dic[i] > 0: return []; return res;

Great solution. I found it to be very intuitive. Here is a cleaned up version.
def findOrder(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: List[int] """ g = {i:set() for i in range(0, numCourses)} g_inv = collections.defaultdict(set) for i, j in prerequisites: g[i].add(j) g_inv[j].add(i) q = queue.Queue() for course in g: if not g[course]: q.put(course) topo_sort = [] while not q.empty(): front = q.get() topo_sort.append(front) for elm in g_inv[front]: g[elm].remove(front) if not g[elm]: q.put(elm) return topo_sort if len(topo_sort) == numCourses else []