一天一大 lee(课程表)难度:中等-Day20200804

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  let mapItem = new Map(), // 出度子集
    mapNum = new Map(),   // 入度连接数
    _result = numCourses,
    startList = [],
    len = prerequisites.length;

  // 初始化入度连接数 与 出度子集
  for (let i = 0; i < numCourses; i++) {
    mapItem.set(i, []);
    mapNum.set(i, 0);
  }

  // 填充入度、出度数据
  for (let i = 0; i < len; i++) {

    // prerequisites[1]  需要在  prerequisites[0] 之前
    //   before -> after
    //   before（出度） -> after (入度)
    let after = prerequisites[i][0],
      before = prerequisites[i][1],
      afterValue = mapNum.get(after),
      beforeValue = mapItem.get(before);

    mapItem.set(before, [...beforeValue, after])
    mapNum.set(after, afterValue + 1)

  }

  // 取出不依赖其他课的元素
  for (let [key, value] of mapNum) {
    if (value === 0) startList.push(key);
  }

  while (startList.length) {
    // 枚举选修不依赖未学习的课的元素
    let item = startList.shift(),
      nextItem = mapItem.get(item);
      // 枚举一轮带选课减一
    _result--;

    if (nextItem && nextItem.length) {
      // 尝试本轮所有选课可能，遇到选择后存在入度为0的元素，
      // 则推进枚举list，之后尝试按照这种路线选课
      for (let i = 0; i < nextItem.length; i++) {
        let nextNum = mapNum.get(nextItem[i]) - 1;
        mapNum.set(nextItem[i], nextNum);
        if (nextNum === 0) {
          startList.push(nextItem[i]);
        }
      }
    }
  }
  // 是否选择了所有课程
  return _result === 0;
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
  let map = new Map(),
    valid = true,
    visited = Array(numCourses).fill(0);

  for (let i = 0; i < numCourses; i++) {
    map.set(i, [])
  }
  // 查询每个课程的的前置课程 即可能的出度子集
  for (let i = 0; i < prerequisites.length; i++) {
    let after = prerequisites[i][0],
      before = prerequisites[i][1],
      beforeValue = map.get(before);
    map.set(before, [...beforeValue, after])
  }

  // 循环为被学习的课程检修是否存在 闭环
  for (let i = 0; (i < numCourses) && valid; i++) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }

// 输入的课程标记选择1
  function dfs(u) {
    visited[u] = 1;
    for (let v of map.values) {
      // 如果前置课程未被选择过则先选择前置课程
      if (visited[v] === 0) {
        dfs(v);
        if (!valid) {
          return;
        }
      } else if (visited[v] === 1) {
        // 如果前置元素同样被标记1，则说明在找u的前置课程v是v的前置课程也同样依赖未选修的前置课程
        valid = false;
        return;
      }
    }
    // 完成前置课程查询标记该课程完成2
    visited[u] = 2;
  }

  // 默认成功，存在闭环则返回失败
  return valid;
};