1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

  • 本题属于 图论 中的 有向图拓扑排序 问题,可用 Kahn 算法(BFS) 解决;其本质也可视为一种“贪心”选择:每次都优先取当前 入度为 0 的课程(没有未完成的前置要求)。

  • 建图方式:将依赖 [a, b] 视为一条 b → a 的有向边(先修 b,后修 a),并统计每个节点的入度。

  • 算法步骤(Kahn):

    1. 统计入度,所有入度为 0 的课程入队;
    2. 不断出队,加入答案序列,并把它指向的后继课程入度减 1;若减到 0,再入队;
    3. 最终若输出数量等于课程总数,得到一个可行顺序;否则存在环(如 [ [2,1],[1,2] ]),返回空数组。

P3703.第1题-前置课程

    1000ms Tried: 50 Accepted: 12 Difficulty: 4 所属公司 : B站
    算法与标签>拓扑排序

题目内容

为了毕业你需要选择 nnn 门课程,这 nnn 门课程中存在一定的依赖关系,例如想要完成 BBB 课程,必须先完成 AAA 课程,请你找出一个可以完成全部课程的顺序,如果无论如何选择都无法完成全部课程则返回空数组。

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

数据范围:1≤n<20001≤n<20001≤n<2000,依赖关系的数量满足 0≤m≤n∗(n−1)0 ≤ m ≤n*(n -1)0≤m≤n∗(n−1) ,保证不会有一组一模一样的依赖关系。

样例1

输入

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

输出

[0,1,2]

样例2

输入

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

输出

[0,1,2,3]

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 75ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?