1. 什么是拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件： 1、每个顶点出现且只出现一次。 2、若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

2. 拓扑排序原理

实现拓扑排序一般有两种思路，一种是基于贪心（BFS），一种是基于DFS

2.1 贪心

1、从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。 2、从图中删除该顶点和所有以它为起点的有向边。 3、重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。 拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。 通常，一个有向无环图可以有一个或多个拓扑排序序列。

伪代码：
TOPOLOGICAL-SORTING-GREEDY(g)
  let inDegree be every verties inDegree Array
  let stack be new Stack
  let result be new Array
  for v equal to every vertex in g
    if inDegree[v] == 0
      stack.push(v)
  end
  while stack.empty() == false
    vertex v = stack.top()
    stack.pop()
    result.append(v)
    for i equal to every vertex adjacent to v 
      inDegree[i] = inDegree[i] - 1
      if inDegree[i] == 0
        stack.push(i)
    end
  end
  return result.reverse()

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数。

2.2 DFS

伪代码：
DFS-IMPROVE(v,visited,stack)
  visited[v] = true
  for i equal to every vertex adjacent to v
    if visited[i] == false
      DFS-IMPROVE(i,visited,stack)
  end
  stack.push(v)

DFS（改良）一个有用的特点是，对于两个顶点A、B，存在A到B的路径，而不存在B到A的路径，则从记录的顺序中取出的时候，一定会先取出顶点A，再取出顶点B。

利用此特性，我们可以这样实现拓扑排序：

伪代码：
TOPOLOGICAL-SORTING-DFS(g)
  let visited be new Array
  let result be new Array
  let stack be new Stack
  for v equal to every vertex in g
    if visited[v] == false
      DFS-IMPROVE(v,visited,stack)
  end
  while stack.empty() == false
      result.append(stack.top())
      stack.pop()
  end
  return result

时间复杂度:Θ(V+E)，V表示顶点的个数，E表示边的个数。
此方法相比贪心而言，最大的缺点是：无法检查图中是否存在环路。

210. 课程表 II

现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2, [[1,0]]

输出: [0,1]

解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]

输出: [0,1,2,3] or [0,2,1,3]

解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。

 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 保存每个点的入度即 对于课程a,学完后才可以学习b,c，那么a的入度为2
        vector<int> degree(numCourses,0);   
        // 保存每个点的指向，对于课程a,学完后才可以学习b,c，那么adjacent[a] = [b,c]
        vector<vector<int>> adjacent(numCourses);
        for (int i=0;i<prerequisites.size();i++)
        {
            degree[prerequisites[i][0]]++;
            adjacent[prerequisites[i][1]].emplace_back(prerequisites[i][0]);
        }
        return bfs(adjacent,degree);
    }
    vector<int> bfs(vector<vector<int>>&adjacent,vector<int>& degree)
    {
        // 保存入度为0的点作为遍历备选点
        stack<int> zero_degree;
        vector<int> res;
        for(int i =0;i<degree.size();i++)
        {
            // 0度的入栈
            if (degree[i]==0) zero_degree.push(i);
        }
        while (!zero_degree.empty())
        {
            // 遍历一个入度为0的节点并弹出栈
            int tmp = zero_degree.top();
            zero_degree.pop();
            res.emplace_back(tmp);
            // 遍历这个节点的邻接点
            for (auto& i:adjacent[tmp])
            {
                degree[i]--;
                // 遍历一次入度减一 为0时入栈
                if(degree[i]==0) zero_degree.push(i);
            }
        }
        // 如果最后还存在大于0的栈则说明有环无法拓扑
        return res.size()==degree.size()?res:vector<int>();
    }
};

841. 钥匙和房间 EASY

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，…，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]

输出: true

解释:

我们从 0 号房间开始，拿到钥匙 1。

之后我们去 1 号房间，拿到钥匙 2。

然后我们去 2 号房间，拿到钥匙 3。

最后我们去了 3 号房间。

由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：[[1,3],[3,0,1],[2],[0]]

输出：false

解释：我们不能进入 2 号房间。

#dfs
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = [1 for _ in range(len(rooms))]
        self.dfs(rooms,visited,0)
        return sum(visited) == 0
    def dfs(self,rooms,visited,cur):
        if not visited[cur]:return;
        visited[cur] =0
        for i in rooms[cur]:
            self.dfs(rooms,visited,i)

#bfs
from collections import deque
class Solution:
    def canVisitAllRooms(self, rooms):
        vistied = [1 for _ in range(len(rooms))]

        que = deque()
        que.append(0)
        while que:
            size = len(que)
            for i in range(size):
                cur = que.popleft()
                if vistied[cur] == 0:
                    continue
                vistied[cur] = 0
                que.extend(rooms[cur])
        return sum(vistied) == 0

if __name__ == '__main__':
    s = Solution()
    print(s.canVisitAllRooms([[1], [2], [3], []]))
    print(dir(deque))

    '''
    True
['__add__', '__bool__', '__class__', '__contains__', '__copy__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', 
'__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft', 'index', 'insert', 'maxlen', 'pop', 
'popleft', 'remove', 'reverse', 'rotate']
    '''