Course Schedule

有向图的查环问题，DFS思路比较直接

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        store = {}
        recStack = [0] * numCourses
        color = [0] * numCourses

        for con, pre in prerequisites:
            store.setdefault(pre, [])
            store[pre].append(con)

        for i in xrange(numCourses):
            if i not in store:
                continue
            if not color[i]:
                if self.DFS(i, store, color, recStack):
                    return False

        return True

    def DFS(self, node, store, color, recStack):
        recStack[node], color[node] = 1, 1
        for neighbor in store[node]:
            if neighbor not in store:
                continue
            if recStack[neighbor]:
                return True
            if not color[neighbor] and self.DFS(neighbor, store, color, recStack):
                return True
        recStack[node] = 0
        return False

Course Schedule II

这道题是就是有向图的纯拓扑排序，而拓扑排序一般有两种方法，第一种是用DFS对整个图进行后序遍历（即backtracking），第二种就是BFS做法，也就是对图的出入度进行统计，最后通过计算出入度得到正确的结果，这里先介绍第二种，因为BFS是拓扑排序的一般性做法

class Solution(object):
    def findOrder(self, n, pres):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        ind = [[] for _ in xrange(n)]                            # 入度需要统计所有的指向的结点
        oud = [0] * n                                            # 出度只需要统计所有指向此节点的结点个数

        for con, pre in pres:                                    # 对结点出入度进行统计
            ind[pre].append(con)
            oud[con] += 1

        res = []                                                 # 先枚举所有没有出度的点并将它们放入结果里面
        for key in xrange(n):                                    # 没有出度意味着此节点一定是一个起始结点
            if not oud[key]:
                res.append(key)

        l = 0
        while l != len(res):                                     # 统计所有没有出度点的入度数组，对里面结点的
            x = res[l]                                           # 出度逐个减少，先到出度为零的必定在前面，这就是BFS
            for node in ind[x]:
                oud[node] -= 1
                if not oud[node]:
                    res.append(node)
            l += 1
        return res if l == n else []

这里写一种自己的DFS解法，但是在lintcode上相同的题会TLE，因为用list的insert函数的关系吧

class Solution(object):
    def findOrder(self, n, pres):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        store = {}
        color = [0] * n
        recStack = [0] * n
        res = []

        for con, pre in pres:
            store.setdefault(pre, [])                                # 有向图
            store[pre].append(con)

        for key in xrange(n):
            if key not in store:
                continue
            if not color[key]:
                tmp = self.DFS(key, color, recStack, store, res)
                if tmp:
                    return []

        for key in xrange(n):
            if not color[key]:
                res.append(key)                                      # 没遍历过的结点肯定是孤点，放最后也可

        return res

    def DFS(self, key, color, recStack, store, res):
        color[key], recStack[key] = 1, 1
        for node in store[key]:
            if node not in store:
                continue
            if not color[node] and self.DFS(node, color, recStack, store, res):     
                return True
            elif recStack[node]:                                     # 探到环则返回
                return True

        res.insert(0, key)                                           # 后序遍历
        recStack[key] = 0
        return False