🌀riba2534's Blog
凡事有交代,件件有着落,事事有回音
LeetCode 207 课程表(拓扑排序)

题目链接:课程表

你这个学期必须选修 numCourse 门课程,记为 0numCourse-1

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

示例 1:

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

示例 2:

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

提示:

  1. 输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法
  2. 你可以假定输入的先决条件中没有重复的边。
  3. 1 <= numCourses <= 10^5

思路

这种有先决顺序的工程安排问题一般就是拓扑排序,这道题是拓扑排序的裸题。

方法1:删入度,bfs

拓扑排序有一个显然的算法,每次删除有向无环图中的入度为0的点,直到没有入度为0的点为止。因为如果存在环,则一个点必将同时有入度和出度。

所以这个算法在实现的时候可以使用一个队列,每次把入度为0的点加入队列中,然后遍历这个点所有的出边,并删除掉这个点的入度。如果点的进队次数等于点数,则证明此图无环。

方法2:深搜

每一个点开始进行深搜,如果搜到了自己,则存在环。

不存在环时再搜的过程中需要标记路线。

代码

bfs删入度:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
    {
        vector<vector<int>> e(numCourses);
        vector<int> in(numCourses, 0);
        for (auto point : prerequisites)
        {
            int u = point[0], v = point[1];
            e[u].push_back(v);
            in[v]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++)
            if (!in[i])
                q.push(i);
        int cnt = 0;
        while (!q.empty())
        {
            cnt++;
            int u = q.front();
            q.pop();
            for (auto v : e[u])
                if (!--in[v])
                    q.push(v);
        }
        return cnt == numCourses;
    }
};

dfs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
public:
    vector<int> vis;
    int dfs(int u, vector<vector<int>> &e)
    {
        vis[u] = -1;
        for (auto v : e[u])
        {
            if (vis[v] == -1)
                return 0;
            else if (!vis[v] && !dfs(v, e))
                return 0;
        }
        vis[u] = 1;
        return 1;
    }
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites)
    {
        vector<vector<int>> e(numCourses);
        vis = vector<int>(numCourses, 0);
        for (auto point : prerequisites)
        {
            int u = point[0], v = point[1];
            e[u].push_back(v);
        }
        for (int u = 0; u < numCourses; u++)
            if (!vis[u])
                if (!dfs(u, e))
                    return false;
        return true;
    }
};


最后修改于 2020-08-04

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。