欢迎访问LeetCode题解合集

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

• 1 <= numCourses <= 10^5

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• prerequisites[i] 中的所有课程对 互不相同

题解：

判断有向图是否存在环。

法一：

深搜。

每个节点有三种状态，未遍历，正在遍历，已经遍历。

搜索过程中遇到 正在遍历 状态的邻接节点，即可判断存在环。

时间复杂度：$O(n + m)$

额外空间复杂度：$O(n + m)$

class Solution {
public:
    vector<vector<int>> g;
    vector<int> vis;
    bool dfs( int u ) {
        vis[u] = 1;
        for ( auto v : g[u] ) {
            if ( !vis[v] ) {
                if ( !dfs(v) )
                    return false;
            } else if ( vis[v] == 1 )
                return false;
        }
        vis[u] = 2;
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        g = vector<vector<int>>(numCourses);
        vis = vector<int>(numCourses);
        for( auto& it : prerequisites ) {
            g[it[0]].emplace_back( it[1] );
        }
        for( int i = 0; i <numCourses; ++i )
            if ( !vis[i] && g[i].size() && !dfs(i) ) return false;
        return true;
    }
};
/*
时间：20ms，击败：95.21%
内存：13.4MB，击败：31.54%
*/

法二：

拓扑排序。

如果不存在环，那么所有节点都会入队出队一次，否则存在环。

class Solution {
public:
    vector<vector<int>> g;
    vector<int> deg;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        deg = vector<int>(numCourses);
        g = vector<vector<int>>(numCourses);
        for( auto& it : prerequisites ) {
            g[it[0]].emplace_back(it[1]);
            ++deg[it[1]];
        }
        queue<int> q;
        for ( int i = 0; i < numCourses; ++i )
            if ( !deg[i] ) q.push( i );
        int num = 0, u;
        while ( q.size() ) {
            u = q.front();
            q.pop();
            ++num;
            for ( auto& v : g[u] ) {
                if ( --deg[v] == 0 )
                    q.push( v );
            }
        }
        return num == numCourses;
    }
};
/*
时间：16ms，击败：98.90%
内存：12.9MB，击败：46.96%
*/