/**
   * @param {number} numCourses
   * @param {number[][]} prerequisites
   * @return {boolean}
   */
  var canFinish = function (numCourses, prerequisites) {
      /**
     * ******DFS方法和Topological 深度优先与拓扑排序法******
     *         **     **           
     *        *****************      
     *      **        **             
     *    **          **          
     *      *********************     
     *             ** ** **          
     *            **  **  **            
     *           **   **   **          
     *          **    **    **          
     *         **     **     **    
     * ******DFS方法和Topological 深度优先与拓扑排序法******
     */
    //1.拓扑排序解决
    function Topological(numCourses, prerequisites){
        //创建邻接矩阵
        var adjacencyMatrix = new Array(numCourses);
        var queue = [];
        for (let i = 0; i < numCourses; i++) {
        adjacencyMatrix[i] = new Array(numCourses);
        adjacencyMatrix[i].fill(0);
        };
        for (let i = 0; i < prerequisites.length; i++) {
        adjacencyMatrix[prerequisites[i][1]][prerequisites[i][0]] = 1;
        }
        //找到入度为0的点入队列     遍历j:0->n列;
        for (let j = 0; j < numCourses; j++) {
        let count = 0;
        for (let i = 0; i < numCourses; i++)
            if (adjacencyMatrix[i][j] == 1)
            count++;
        if (count == 0)
            queue.push(j);
        }
        //从队首开始移出元素，然后改变邻接矩阵
        while (queue.length) {
        let current = queue.shift();
        for (let j = 0; j < numCourses; j++) {
            if (adjacencyMatrix[current][j] == 1) {
              adjacencyMatrix[current][j] = 0;
              for (let i = 0; i < numCourses; i++) {
                  if (adjacencyMatrix[i][j] == 1) {
                    break;
                  } else {
                    if (i == numCourses - 1) {
                        queue.push(j);
                    }
                  }
              }      
            }        
        }
      }
        //查看矩阵是否全为0;
        for (let i = 0; i < numCourses; i++) {
        for (let j = 0; j < numCourses; j++) {
            if (adjacencyMatrix[i][j] == 1) return false;
        }
        if (i == numCourses - 1) return true;
        }
    }

    //2.深度优先DFS遍历，只要不存在环，就成功
  function DFS(numCourses, prerequisites) {
      /**从一个节点(入度为0的点)开始，深度优先访问所有节点。 但是可能一个闭环中所有节点入度为0
     *  不过如果碰到环了就直接回退吧，不需要遍历完了
     * @param {number} node 节点名
     */
    function dfs(node) {
      var nextNodes = adjacencyTable.get(node);
      if (nextNodes.length == 0) {
        stats.set(node, -1)
        return;
      };
      stats.set(node, 1)            
      for (let i = 0; i < nextNodes.length; i++) {
        if (result == false) return;
        if (stats.get(nextNodes[i]) == 0) {
          dfs(nextNodes[i])
        } else if (stats.get(nextNodes[i]) == 1) {
          result = false;
          break;
        } else if (stats.get(nextNodes[i]) == -1) {
          continue;
        }
      }
      stats.set(node, -1);
      return;
    }
    //创建邻接表
    var adjacencyTable = new Map()
    var queue = new Array(numCourses) //记录节点入度数
    queue.fill(0) //初始化入度为0的点值为0。
    var stats = new Map(); //key:节点,value:访问状态。0未被访问，1正在访问，-1已经被其他访问
    //最后状态全为-1，则表示访问完了。
    var result = true; //记录是否有环。和是否全部访问完。true 为遍历到的节点是无环的
    for (let i = 0; i < numCourses; i++) {
      adjacencyTable.set(i, []);
      stats.set(i, 0);
    }
    for (let i = 0; i < prerequisites.length; i++) {
      adjacencyTable.get(prerequisites[i][1]).push(prerequisites[i][0]);
    }
    // console.log(‘邻接表：‘, adjacencyTable)
    //找出入度为0的点
    adjacencyTable.forEach((val, key) => {
      val.forEach((item, index) => {
        queue[item]++
      })
    })
    // console.log(‘入度数：‘, queue)
    //从每个入度为0的点开始遍历图
    queue.forEach((item, index) => {
      if (item == 0) {
        dfs(index);
      }
    })
    //查看状态;
    if (result == false) return false;
    // console.log(‘最终状态：‘, stats)
    for (let i = 0; i < stats.size; i++) {
      if (stats.get(i) == 0) return false;
    }
    return true;
  }

    //调用
    //调用
    //调用
    //调用
    //1.拓扑排序解决
    // return Topological(numCourses, prerequisites);

    //2.DFS深度优先
    return DFS(numCourses, prerequisites)    
  };