原题链接:
https://leetcode.cn/problems/course-schedule/description/

解法1:

拓扑排序

基本上照着拓扑排序模板来就行了
就是题意稍微理解一下
prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
所以 b -> a

拓扑排序步骤:

  1. 入队所有入度为0 的点
  2. bfs 取出队头t -> 每取出一次队头说明有一个数已加入排序好的序列
  3. 枚举t的所有出边 t->j
    1. 删掉 t->j 即让 d[j]– (d[j] j的入度)
    2. if d[j] == 0 -> 说明j之前所有点均以排好序 -> j 入队
  4. 如果图中存在环则无法全部入队 反之则都可以入队
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
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
拓扑排序 
学a 需要先学b  a <- b
*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 图
        vector<vector<int>>g;
        // 入度
        vector<int>d;
        g.resize(numCourses);
        d.resize(numCourses);

        for(auto p : prerequisites){
            // b -> a
            g[p[1]].push_back(p[0]);
            d[p[0]]++;
        }

        queue<int>q;

        for(int i = 0 ; i < numCourses ; i++){
            if(d[i] == 0){
                q.push(i);
            }
        }

        while(q.empty() == false){
            auto t = q.front();

            // 每次出队 代表完成一次排序 numCourse--
            numCourses--;
            q.pop();
            for(auto v:g[t]){
                d[v]--;
                if(d[v] == 0){
                    q.push(v);
                }
            }
        }

        return numCourses == 0;
        
    }
};

leetcode210 课程表2

原题链接:
https://leetcode.cn/problems/course-schedule-ii/

和上一题都一样就是要返回具体拓扑的顺序

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
拓扑排序
1. 入度为0入队
2. 队头j出队 加入 结果
3. 遍历j 所有边 入度-1 
4. 入度为0再次入队 
*/
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>>g;
        vector<int>d;
        g.resize(numCourses);
        d.resize(numCourses);


        for(int i = 0; i < prerequisites.size(); i++){
            // a <- b
            int a = prerequisites[i][0], b = prerequisites[i][1];
            g[b].push_back(a);
            d[a]++;
        }         

        

        queue<int>q;
        
        for(int i = 0; i < numCourses ; i++){
            if(d[i] == 0){
                q.push(i);
            }
        }
        
        vector<int> ans;
        while(q.empty() == false){
            auto t = q.front();
            ans.push_back(t);
            q.pop();
            for(auto j : g[t]){
                d[j]--;
                if(d[j] == 0){
                    q.push(j);
                }
            }
        }

        return ans.size() == numCourses ? ans : vector<int>();
    }
};

1462. 课程表 IV

原题链接:
https://leetcode.cn/problems/course-schedule-iv/

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
    在拓扑排序的基础 加一个数组f[][] 用于记录各个节点之间的可达性
*/
class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<bool>>f(numCourses,vector<bool>(numCourses,false)); 
        vector<int>d(numCourses);
        vector<vector<int>>g(numCourses);
        
        for(int i = 0 ; i < prerequisites.size() ; i++){
            int a = prerequisites[i][0], b = prerequisites[i][1];
            g[a].push_back(b);
            d[b]++;
        }

        queue<int>q;

        for(int i = 0 ; i < numCourses ; i++){
            if(d[i] == 0){
                q.push(i);
            }
        }


        while(q.empty() == false){
            auto t = q.front();
            q.pop();
            for(auto j : g[t]){
                // j 为t 的边 因此 t,j 可达
                f[t][j] = true;
                for(int h = 0 ; h < numCourses ; h++){
                    // t 可以到j 
                    // 那么存在如果一点 h 
                    // 如果 h 可以到 t  
                    // 那么 h就可以顺着t 到达j
                    if(f[h][t]){
                        f[h][j] = true;
                    }
                }
                d[j]--;
                if(d[j] == 0){
                    q.push(j);
                }
            }
        }

        vector<bool> ans;

        for(auto &qry : queries){
            ans.push_back(f[qry[0]][qry[1]]);
        }

        return ans ;
    }
};