【LeetCode 207】课程表（有向无环图 DAG、拓扑排序）

题面：

Link：LeetCode 207 课程表

思路：

首先很容易想到如果图中存在有向环，则表示这个环里的课是没法学习的（因为环里的课都在等待自己的前置课被学习）。
例如：$0\to 1\to 2\to 0$

简单用拓扑排序的思想解释一下：容易想到只有 入度为 0 的顶点（课）是可以一开始就直接学习的。如果有顶点 $u$ 被遍历了（$u$ 课程被学习了），其指向的所有邻接点的入度就可以减一（邻接点的前置课 $u$ 已经学习了，因此 $u$ 对它们已经没有约束了）。

因此，只有 有向无环图（DAG） 才是合法的。
有个性质：能拓扑排序的图一定是有向无环图（DAG），有向无环图一定能拓扑排序。

DAG的判断一般就两种方法：

1. 用入度搞个拓扑排序
2. 可以直接 DFS 判断是否存在 有向环，对图进行一遍 DFS，在得到的 DFS 树上看看有没有连向祖先的非树边（返祖边）。如果有的话，那就有环了。简单来说，直接判断 DFS 的搜索过程中是否有结点被二次遍历了，有就是出现环了。

代码：

拓扑排序：

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> d(numCourses, 0);
    vector<vector<int>> edges(numCourses);
    for(const auto& edge : prerequisites) {
        edges[edge[1]].emplace_back(edge[0]);
        ++ d[edge[0]];
    }
    int visited = 0;
    queue<int> q;
    for(int i = 0; i < numCourses; ++i)
        if(!d[i])
            q.push(i);
    while(!q.empty()) {
        ++visited;
        int u = q.front(); q.pop();
        for(const auto& v : edges[u]) {
            --d[v];
            if(!d[v]) q.push(v);
        }
    }
    return visited == numCourses;
}

DFS判断环：

class Solution {
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

public:

    void dfs(int u) {
        visited[u]=true;
        if(!valid) return ;
        for(const auto &v : edges[u]) {
            if(visited[v] == 1) {
                valid = false;
                return ;
            }
            if(valid && !visited[v]) dfs(v);
        }
        visited[u]++;
        return ;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses, vector<int>());
        visited.resize(numCourses, false);

        for(const auto &edge : prerequisites) 
            edges[edge[1]].emplace_back(edge[0]);
        
        for(int i=0;i<numCourses && valid;i++)
            if(!visited[i])
                dfs(i);
        
        return valid;
    }
};