day9 课程表

有点忙，又是作业又是组会又是每日一题，之前给 tensorflow 鼓捣着配环境，golang 的东西也找好了但没开始学。
不过感觉主要还是因为我作业一直没做拖到现在。

读题

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
  请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思路

是一道应用题，偏向于实际情境，如果对涉及的算法不熟悉，就会在情景里绕不出去。
有二维数列 vector<vector<int>> prerequisites，可以被视作是矩阵；存在一对多的前置关系，一个课程可以是多个课程的前置条件，但一个课程不会有多个前置，考虑构建树，和上一题类似，使用哈希表存储 key 到子节点指针映射。
思路是：

1. 遍历，写入树
2. 深度优先搜索，寻找深度最大的树
3. 判断是否与 prerequisites.size 相同

存在问题：假如课程互为前提，或者间接互为前提，会成环，那怎么办？

---

考虑使用图结构，如果成环，则可以同时选？

---

等等，先思考一下题目要求的结果。
要求是：可以修完所有课程，也就是说不会有课程的前置课程不被满足；换言之，所有节点或者课程必须成环，因为没有课程不需要前置，

---

不，这不对，有课程是没有前置的，判断的点在于 numCourses 是否足够容纳所有课程。
而且，按照给出的例子，成环是不被允许的。那么，我可以使用一个有向图，判断是否成环；如果成环，则一定不可以。
那么，numCourses 的作用体现在哪里？

---

总而言之，先把成环判断写出来，因为成环了是肯定不可以的，numCourses 的之后再说。
百度搜索有向图的写法（我只知道它的存在，不知道实现方法）。
在百度过程中得知了“拓扑排序”，不是寻找环，而是从入度为 0 的节点开始，一点一点向下走，找到连接的点，并认为如果一个节点所有入度节点全部入度为 0，那么它也可以被视作是入度为 0；然后循环。按这样搜索能够排除所有的环，因为环中的节点无论怎么操作，入度永远都是正数，不会到零。
当然，本质还是判断是否有环，因为 numCourses 是指定的值而不是一个范围。
过程是：

1. 创建二维矩阵 pic 作为有向图，数列 in 作为每个节点的入度；pic 和 in 的大小应当是 numCourses，因为只能选择 numCourses 个课程。这个过程中，入度是核心。
2. 遍历 prerequisites，形成有向图
   1. 读取
   2. 记录
   3. 入度增加
3. 找到入度为 0 的课程，记录在 in_0_node 里，这是一个队列，保存的是图矩阵中的序号，而不是课程 id。
4. “拓扑排序”，这部分的代码是抄的。有一个计数器记录入度为 0 或者即将为 0 的课程个数。对于 in_0_node 中的每一个课程：
   1. 提取队首的课程 curr，将其出队，计数器加一
   2. 当前课程可以作为其他课程的前置课程。寻找其他以当前课程作为前置的课程，将其入度减少；如果其入度为 0，所有前置都被满足，那么可以学这门课。
   3. 将入度为 0 的课程入队。
5. 如果所有课程都能学习，计数器 count 恰好等于 numCourses 而不是大于，那么就返回 True

于是有代码：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> pic(numCourses);
        vector<int> in(numCourses, 0);
        
        for (vector<int>& course_list : prerequisites) {
            int course = course_list[0];      // 要学习的课程
            int prerequisite = course_list[1]; // 先修课程
            pic[prerequisite].push_back(course); // 先修课程指向后续课程
            in[course]++;     // 增加后续课程的入度
        }
        
        // 使用队列存储所有入度为0的节点（可以直接学习的课程）
        queue<int> in_0_node;
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                in_0_node.push(i);
            }
        }
        
        // 记录能够学习的课程数量
        int count = 0;
        
        // 拓扑排序
        while (!in_0_node.empty()) {
            int curr = in_0_node.front();
            in_0_node.pop();
            count++;
            
            // 处理当前课程的所有后续课程
            for (int next : pic[curr]) {
                in[next]--;        // 减少入度
                if (in[next] == 0) { // 入度为0时加入队列
                    in_0_node.push(next);
                }
            }
        }
        
        // 如果所有课程都能学习，则返回true
        return count == numCourses;
    }
};

结果

0 ms 用时？这不对吧？
18.81 MB 空间。
虽然结果很完美，核心的代码是抄来的，心有愧疚。

官方题解

这是一个拓扑排序问题，对于有向无环图进行排序。

给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：
对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在 v 的前面。
那么称该排列是图 G 的「拓扑排序」。

也就是说，一个图想要有拓扑排序，那么其中一定不能有环。

方法一：深度优先搜索

用一个栈来存储所有已经搜索完成的节点
假设我们当前搜索到了节点 u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把 u 入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 u 的相邻节点的前面。因此对于 u 这个节点而言，它是满足拓扑排序的要求的。
这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

---

不是我说，要是让我自己来想，我是想破头也想不到适合栈的特性啊。
怎么想到的？
是有向图拓扑排序的定势。不过，我不知道需要拓扑排序，那么也自然想不到使用栈。

---

节点有状态：

• 未搜索
• 搜索中，还存在相邻节点
• 已入栈

过程是：

1. 所有节点默认为未搜索
2. 选择一个节点，标记为搜索中，搜索其相邻节点。如果相邻节点：
   1. 未搜索：开始搜索其相邻节点
   2. 搜索中：发现一个环，直接返回 false，不存在拓扑排序
   3. 已入栈：相当于成功
3. 如果所有节点已经入栈，那么返回 True。

当然，因为只需要判断是否存在拓扑排序，所以栈本身是不需要的，只需要标记状态

方法二: 广度优先搜索

我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。

---

和我抄的方法如出一辙。

---

是一种正向的思路，也是比较容易理解和想到的。

收获

我自己想到了要使用有向图，不过不知道怎么写。
学习了：

1. 有向图的写法
2. 拓扑排序的写法和情景