《五月集训》(第三十天)——拓扑排序

文章目录

  • 前言
  • 一、练习题目
  • 二、算法思路
  • 三、源码剖析

前言

        欢迎大家积极在评论区留言发表自己的看法,知无不言,言无不尽,养成每天刷题的习惯,也可以自己发布优质的解题报告,供社区一同鉴赏,吸引一波自己的核心粉丝。
        今天是五月集训第三十天:拓扑排序

一、练习题目

        207. 课程表
        1976. 到达目的地的方案数

二、算法思路

  • 1、207. 课程表:这道题录播解题4分钟,我花了一上午整明白了拓扑排序。
  • 2、1976. 到达目的地的方案数:这道题我先一下

三、源码剖析

// 207. 课程表
class Solution {
    #define maxn 100010
    vector<int> edges[maxn]; 
    int deg[maxn]; //(1)
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        queue<int> q;
        for(int i = 0; i < numCourses; ++i) {
            edges[i].clear();
            deg[i] = 0;
        } //(2)

        for(int i = 0; i < prerequisites.size(); ++i) {
            edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
            ++deg[prerequisites[i][0]];
        } //(3)

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

        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = 0; i < edges[u].size(); ++i) {
                int v = edges[u][i];
                if(--deg[v] == 0) {
                    q.push(v);
                }
            }
        } //(5)
        for(int i = 0; i < numCourses; ++i) {
            if(deg[i]) {
                return false;
            }//(6)
        }
        return true;
    }
};
  • 1、定义邻接表数组(也或者叫一条边吧)、入度数组;
  • 2、做好初始化;
  • 3、构建边,举题目中的例子:要学两门课,[1, 0]表示要学“1”这门课你得先修完“0”,抽象出我从零这画出一个箭头指向了1。并且把1的入度要增加1,表明它有先修课程;
  • 4、这一步干的事意思呢是,你看上面的例子,“0”这门课是没有先修的直接学起来,用一个队列来记录;
  • 5、队列不空说明有可以学的课,然后遍历所有学完当前课程的下一门课,把他们入度-1,如果有入度减到0了说明这门课我们可以接着学了,它的先修课都学完了,放入队列继续直达队列空了;
  • 6、队列空说明我把能学的都学完了,但还有环需要判断,这一步是判断入度不为0的说明肯定是个环,就是类似[0,1],[1,0]要学“0”先学“1”,要学“1”先学“0”构成了环,那这样肯定是咋都学不好,就返回false。
// 1976. 到达目的地的方案数

  • 1、

你可能感兴趣的