首页 > 试题广场 >

检测循环依赖

[编程题]检测循环依赖
  • 热度指数：1456 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
为了毕业你需要选择 n 门课程，这 n 门课程中存在一定的依赖关系，例如想要完成 B 课程，必须先完成 A 课程，请你找出一个可以完成全部课程的顺序，如果无论如何选择都无法完成全部课程则返回空数组。

依赖关系以如下方式输入：
[[2,1],[3,2]]
即要完成课程 2 ，必须先完成 1 ， 要完成课程 3 ，必须先完成课程 2，答案 [1,2,3] 即可。
但也可能出现类似
[[2,1],[1,2]]
要完成课程 2 ，必须先完成 1 ，要完成课程 1 ，必须先完成课程 1 ，则无解，返回一个空数组即可。

数据范围： 1 \leq n \leq 2000 \ ，依赖关系的数量满足 0 \leq m \leq n*(n-1) \ ，保证不会有一组一模一样的依赖关系。
示例1

输入

[[1,0],[2,1]],3

输出

[0,1,2]
示例2

输入

[[1,0],[2,1]],4

输出

[0,1,2,3]

说明

返回 [3,0,1,2] ，[0,3,1,2] , [0,1,3,2]  也都合法
示例3

输入

[[1,0],[0,1]],2

输出

[]

说明

  存在环
算法知识视频讲解
开通博客
头像 xqxls
发表于 2022-01-19 17:39:03
题意整理 给定n门课程，这n门课程中存在一定的依赖关系，例如想要完成B课程，必须先完成A课程。依赖关系存储在一个数组里。 找出可以完成所有课程的一个顺序列表，如果不能完成所有课程，返回一个空数组。 方法一（深度优先搜索） 1.解题思路 新建一个邻接表，记录所有课程对应的后置课程。新建一个vis 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 WilsonKalven
发表于 2023-08-11 07:12:49
function findOrder( prerequisites , n ) { // write code here // 构建图 const res = [] let hasCycle = false const path = new Array(n) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Coming680
发表于 2022-03-21 16:01:56
拓扑排序的简单运用。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prerequisites int整型vector<vec 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Ivy2019
发表于 2022-10-01 13:03:44
描述 为了毕业你需要选择 n 门课程，这 n 门课程中存在一定的依赖关系，例如想要完成 B 课程，必须先完成 A 课程，请你找出一个可以完成全部课程的顺序，如果无论如何选择都无法完成全部课程则返回空数组。 依赖关系以如下方 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 苦行潜修者
发表于 2024-04-22 11:23:01
using System; using System.Collections.Generic; class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pre 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 CroMarmot
发表于 2022-01-05 11:58:40
题意 给点之间的依赖关系，求拓扑排序 限制： 点的个数不大于2000 方法 循环遍历(TLE) 每次枚举点，找入度为零的，找到则标记。 如此循环直到找不到或者完全输出. 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客897940647号
发表于 2022-04-07 08:49:40
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param prerequisites int整型二维数组 # @param n int整型 # @return int整型一维数组 # 步骤 # 1.cur,pre都在rs，若cur在pre前面， 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 代码界的小白
发表于 2022-02-20 14:44:36
题目主要信息 为了毕业你需要选择 n 门课程，这 n 门课程中存在一定的依赖关系，例如想要完成 B 课程，必须先完成 A 课程，请你找出一个可以完成全部课程的顺序，如果无论如何选择都无法完成全部课程则返回空数组。 依赖关系以如下方式输入： [[2,1],[3,2]] 即要完成课程 2 ，必须先完成 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 用户抉择
发表于 2022-07-10 10:51:05
class Solution { public:     vector<int> findOrder(vector<vector<int> >& prerequisi 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 youxiwang
发表于 2022-04-03 08:57:47
拓扑排序 三个数据存储的内容： infosMap: 还没安排的课(以及该门课的上下游依赖关系) inEdge: 还没上的上游课程的数量 inEdge==0表示这门课不依赖其他课，或者依赖的课已经上过了(i.e. 加入ans了) neis: 下游的课号 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

图
难度：
4条回答 2677浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号