当前位置: 首页 > article >正文

LeetCode HOT100系列题解之课程表(9/100)

 一、题目 

         课程表. - 力扣(LeetCode)

 二、题目解析        

          想要学习课程Bi,那么就要学习课程Ai,一个前后关系,比较好表示前后关系的就是建图。如果在学A课之前要学B课,学B课之前又要学A课,那么实际上构成了环,因此比较好想到的就是建图后DFS找环

三、题目代码

class Solution {
public:
    static const int N = 5010;
    vector<int> vec[N];
    int color[N];
    
    bool dfs(int u)
    {
        color[u] = 0;
        for(int v : vec[u]){
            if(color[v] == 0) {
                return false;
            }
            else if(color[v] == -1){
                if(!dfs(v))
                    return false;
            }
        }
        color[u] = 1;
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int n = prerequisites.size();
        for(int i = 0; i < n; i ++)
            vec[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        memset(color, -1, sizeof color);

        for(int i = 0; i < numCourses; i ++){
            if(color[i] == -1){
                if(!dfs(i))
                    return false;
            }
        }
        return true;
    }
};


http://www.kler.cn/a/376775.html

相关文章:

  • 2025新年源码免费送
  • RabbitMQ介绍与使用
  • springboot整合拦截器
  • Spring——自动装配
  • 【python基础——异常BUG】
  • 【简博士统计学习方法】第1章:2. 统计学习方法的基本分类
  • MAC电脑的ifconfig输出
  • 浅谈mysql【8.0】链接字符串
  • 用于 Web 开发的 10 个必备 VS Code 扩展
  • iOS用rime且导入自制输入方案
  • linux_电脑一运行程序就死机怎么处理?
  • 锁原理和使用
  • Docker 安装HomeAssistant智能家居系统
  • uni-app实现app展示进度条在线更新以及定时更新提醒
  • 懂前端的都知道这里的门道有多深 - js 的事件循环
  • git am使用详解
  • 共模噪声和差模噪声
  • CentOS 7系统下Redis Cluster集群一键部署脚本发布
  • C++学习笔记----9、发现继承的技巧(六)---- 有趣且令人迷惑的继承问题(7)
  • 爬虫ip与反爬虫的“猫鼠游戏”
  • 萌熊数据科技:剑指脑机转入,开启科技新篇章
  • 机器学习实战:从数据准备到模型部署
  • 网关如何传递信息给微服务
  • 虚拟机安装Ubuntu系统
  • Kafka物理存储机制深度解析
  • 市场分化!汽车零部件「变天」